二维平面上线段与直线位置关系的判定
和点与线段的位置关系的判定类似，在讨论线段与直线的位置关系的时候，也是采用向量的叉积的方法来做的。具体方法是在直线上取两点AB,如下图所示，对于给定的线段CD和CE，不难发现当点C与点E同在直线L（即线段AB）的顺时针方向上(同在逆时针方向上也是成立的)；点C与点D分别在L的不同方向上(一个位于顺时针一个位于逆时针方向上)，此时直线与线段相交；对与线段点落在直线L上的情况在此不做说明，很简单，动手画画就知道了。
Problem：Segments (http://poj.org/problem?id=3304)
给定平面上n条线段，判断是否存在一条直线，使得这n条线段在L上的投影至少有一个公共点。
可能现在你觉得这个问题和线段与直线关系的判定没有什么联系。下面给出具体的分析：先考虑一个特殊的情况，即n=1的时候，如下图，线段AB在直线L上的投影为线段A'B'，则过任意介于A'B'之间的点C'做直线L的垂线必交线段AB与一点C；反之，过线段AB之间任意一点C做直线L的垂线，垂足必定落在A'B'之间。
不难将此结论推广到n条线段的情况，假设存在一满足题意的直线L，则设点A为各个线段在L上投影的公共点，那么过A做一条直线L的垂线L'，则L'必定与n条线段都相交；反之，过所有线段做一个直线L1使其与n条线段均相交，做直线L1的垂线L2，容易发现垂足即为所有n条线段投影的公共点。
这样一来就清晰了，问题转化成了判定是否存在一条直线L，L与n条线段均相交。我们只需枚举n条线段，判定是否均与直线L相交。但是，直线L该如何枚举呢？这里采用的方法也是计算几何中常用到得离散化思想。我们知道计算机只能处理离散的数据，我们没有办法来通过连续的旋转直线L来分别判定是否满足题意。但是我们可以采用离散化的思想：假设任意直线L分别于n条线段相交，我们可以采用将直线L分别向顺时针和逆时针的方向旋转，旋转的时候必须满足于n条线段均相交的限制，直到无法旋转为止。那么，最后直线会和n条线段中的某两条的端点重合。这样，我们就可以通过枚举任意两线段端点确定的直线，从而对问题进行求解。
下面说明一下该问题的两个细节：
<1>、n=1时要特判；
<2>、精度问题，当枚举两线段中的端点距离很接近(<1e-8)的时候，不能作为待选直线判定，原因见下图：
#include<iostream> #include<cstdio> #include<math.h> #define N 110 #define EPS 1e-10 using namespace std; typedef struct Node1 { double x,y; }Point; typedef struct Node2 { Point s,t; }Segment; Segment s[N]; int n; double cross(Point o,Point a,Point b)//求叉积 { return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y); } double dis(Point a,Point b) //求两点距离 { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int judge(Point a,Point b)//判定是否与n条线段均相交 { if(dis(a,b)<EPS) return 0;//细节2 for(int i=0;i<n;i++) if(cross(a,b,s[i].s)*cross(a,b,s[i].t)>EPS)// 精度控制 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",&s[i].s.x,&s[i].s.y,&s[i].t.x,&s[i].t.y); int yes=0; if(n==1) yes=1;//特判 for(int i=0;yes==0&&i<n;i++)//枚举线段定点确定的待选直线 for(int j=i+1;yes==0&&j<n;j++) if(judge(s[i].s,s[j].s)||judge(s[i].s,s[j].t) ||judge(s[i].t,s[j].s)||judge(s[i].t,s[j].t)) yes=1; if(yes) printf("Yes!/n"); else printf("No!/n"); } return 0; }
