题目链接：
http://poj.org/problem?id=3304
题目大意：
给你一些线段，问你能不能找出一条直线，使得这些线段投影到这条直线上至少有一个公共交点。
思路：
这题转化一下其实就是能不能有一条直线穿过所有的线段。由于N比较小（n<=100）所以我们可以枚举每两条线段上的端点形成一条直线，然后看这条直线能否穿过所有的线段。这样问题就变成了直线与线段相交的关系。注意题目中说如果两个点之间距离小于10^-8，就表示这两个点相同。（这是个坑点）。所以要将重点判掉。
代码：
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #define PI acos(-1.0) #define eps 0.00000001 using namespace std; int n; struct Point{ double x,y; Point(double x=0,double y=0):x(x),y(y){} }; struct line{ Point a,b; line(Point a=0,Point b=0):a(a),b(b){} }; line Line[5005]; Point operator + (Point A ,Point B){ return Point(A.x+B.x,A.y+B.y); } Point operator - (Point A,Point B){ return Point(A.x-B.x,A.y-B.y); } int dcmp(double x){ if(fabs(x)<eps)return 0; else if(x<0)return -1; return 1; } bool operator ==(const Point &a,const Point &b){ return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0; } double Dot(Point A,Point B){ return A.x*B.x+A.y*B.y; } double Cross(Point A,Point B){ return A.x*B.y-A.y*B.x; } double Length(Point A){ return sqrt(Dot(A,A)); } double getdistance(Point P,line A){ Point v1=A.b-A.a; Point v2=P-A.a; return fabs(Cross(v1,v2)/Length(v1)); } int LeftofLine(Point P,line A){ //点在直线哪一侧。 Point c1,c2; c1=A.a; c2=A.b; double tmp=(c1.x-c2.x)/(c1.y-c2.y)*(P.y-c2.y)+c2.x; if(tmp>P.x)return 1; else if(tmp<P.x)return 2; else return 4; } bool check(Point A,Point B){ if(A==B)return false; //判重点 line l=line(A,B); int flag=0; for(int i=1;i<=n;i++){ int aa,bb; aa=LeftofLine(Line[i].a,l); bb=LeftofLine(Line[i].b,l); if(aa+bb==2||aa+bb==4){ flag=1;break; } } if(flag)return false; return true; } int main(){ int m; int T; double x1,y1,x2,y2; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); Point A,B; A=Point(x1,y1); B=Point(x2,y2); Line[i]=line(A,B); } int flag=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(check(Line[i].a,Line[i].b)||check(Line[i].a,Line[j].a)||check(Line[i].b,Line[j].a)||check(Line[i].b,Line[j].b)) { flag=1; break; } } } if(flag==0)printf("No!\n"); else printf("Yes!\n"); } }