题意:给出n条线段两个端点的坐标,问所有线段投影到一条直线上,如果这些所有投影至少相交于一点就输出Yes!,否则输出No!。
题解:假设存在一条这样的直线,那么过这条直线的公共投影区域作一条垂线,则该垂线必定与所有线段相交。所以问题变成了如何找这一条直线,然后这条直线必过线段的两个端点。考虑到线段数目不是很多,所以我们只需要枚举所有线段的两个端点组成的直线即可。注意用精度判断点是否重合!
代码:
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const int maxn=5005; const double eps=1e-12; struct Point{ double x, y; Point(double x=0, double y=0):x(x),y(y){} Point operator-(const Point &cmp)const{return Point(x-cmp.x, y-cmp.y);} double operator*(const Point &cmp)const{return x*cmp.x+y*cmp.y;} }; struct Line{ Point s, e; Line(){} Line(Point s, Point e):s(s), e(e){} bool operator <(const Line &cmp)const { return s.x<cmp.s.x; } }; typedef Point Vector; Vector operator +(Vector A, Vector B){return Vector(A.x+B.x, A.y+B.y);} Vector operator -(Point A, Point B){return Vector(A.x-B.x, A.y-B.y);} Vector operator *(Vector A, double p){return Vector(A.x*p, A.y*p);} Vector operator /(Vector A, double p){return Vector(A.x/p, A.y/p);} int dcmp(double x){ if(fabs(x)<eps)return 0;else return x<0?-1:1; } double Cross(Vector A, Vector B){return A.x*B.y-A.y*B.x;} double Area2(Point A, Point B, Point C){return Cross(B-A, C-A);} double dist(Point A, Point B){return sqrt((B-A)*(B-A));} bool line_make_point(Line l1, Line l2){ return dcmp(Area2(l2.s, l1.s, l1.e))*dcmp(Area2(l2.e, l1.s, l1.e))<=0; } int n; Line line[maxn]; Point point[maxn]; bool check(Line l1){ for(int i=0;i<n;i++){ if(line_make_point(l1, line[i])==0)return 0; } return 1; } int main() { int T; scanf("%d", &T); while(T--){ scanf("%d", &n); for(int i=0;i<n;i++){ scanf("%lf%lf%lf%lf", &point[i*2].x, &point[i*2].y, &point[i*2+1].x, &point[i*2+1].y); line[i]=Line(point[i*2], point[i*2+1]); } bool ans=0; for(int i=0;i<n*2;i++){ for(int j=i+1;j<n*2;j++){ if(dcmp(dist(point[i], point[j]))!=0){ if(check(Line(point[i], point[j]))){ ans=1;break; } } } } printf("%s\n", ans?"Yes!":"No!"); } return 0; }