题目：POJ3304
给定n条线段，找出一条直线，能与所有的线段有一个交点（可以在端点处相交）。
思路：
如果存在这么一条直线，必定过平面中的两个点，所以任意穷举两个点所在的直线与所有线段判断是否相交。
Sample Input
3 2 1.0 2.0 3.0 4.0 4.0 5.0 6.0 7.0 3 0.0 0.0 0.0 1.0 0.0 1.0 0.0 2.0 1.0 1.0 2.0 1.0 3 0.0 0.0 0.0 1.0 0.0 2.0 0.0 3.0 1.0 1.0 2.0 1.0
Sample Output
Yes! Yes! No!
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>using namespace std;const int N=210;
const double eps=1E-8;int sig(double d)
{return (d>eps) - (d<-eps);
}struct Point{double x,y;
}point[N];int n;//差积
double cross(Point &c,Point &a,Point &b)
{return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}//判断直线a,b是否与线段cd相交
//0 不想交
//1 规范相交
//2 不规范相交
int segLineCross(Point &a,Point &b,Point &c,Point &d)
{int d1,d2;d1=sig(cross(a,b,c));d2=sig(cross(a,b,d));if((d1^d2)==-2)return 1;if(d1==0 || d2==0) return 2;return 0;} //判断直线与线段所有线段是否相交 bool Test(Point &a,Point &b){int i;if(sig(a.x-b.x==0 && sig(a.y-b.y)==0)) return false;for(i=0;i<2*n;i+=2)if(segLineCross(a,b,point[i],point[i+1])==0)return false;return true;}//测试所有俩点构成的直线 bool Find(){int i,j;for(int i=0;i<2*n;i++)for(int j=0;j<2*n;j++)if(Test(point[i],point[j]))return true;return false;}int main()
{int T;cin>>T;while(T--){cin>>n;for(int i=0;i<2*n;i++)cin>>point[i].x>>point[i].y;if(Find())cout<<"Yes!"<<endl;else cout<<"No!"<<endl;}return 0;
}