poj 3304 Segments--直线和线段相交
/*题意：给一些线段 问你是否存在这样一条直线：所有这些线段在直线上的投影有公共点假设存在 那么过这个点，做这条直线的垂线，这条垂线过所有线段因为所有线段的投影都覆盖这点，因为他们的投影有这个公共点么所以就是找一条直线穿过所有线段所以枚举任意两个点组成的直线 看是否满足要求*/#include<stdio.h>#include<math.h>const double zero=1e-8;struct point{double x,y;};struct segment//线段{point p1,p2;}s[110];point pp[210];//村所有的点int t,n;int equal(point p1,point p2)//判断是否是同一个点{if(fabs(p1.x-p2.x)<=zero&&fabs(p1.y-p2.y)<=zero)return 1;return 0;}double cross(point p,point v1,point v2)//做叉积{return (v2.x-v1.x)*(p.y-v1.y)-(p.x-v1.x)*(v2.y-v1.y);}int sCrossL(point s1,point s2,point l1,point l2)//判断直线是否穿过线段{if(cross(s1,l1,l2)*cross(s2,l1,l2)<=0)return 1;return 0;}int main(){int i,j,k;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;++i){scanf("%lf%lf%lf%lf",&s[i].p1.x,&s[i].p1.y,&s[i].p2.x,&s[i].p2.y);pp[i*2+0].x=s[i].p1.x;pp[i*2+0].y=s[i].p1.y;pp[i*2+1].x=s[i].p2.x;pp[i*2+1].y=s[i].p2.y;}for(i=0;i<2*n-1;i++){for(j=i+1;j<2*n;++j)//枚举点{if(!equal(pp[i],pp[j]))//不是同一个点{for(k=0;k<n;k++)//测试所有的边if(!sCrossL(s[k].p1,s[k].p2,pp[i],pp[j]))break;if(k==n)break;}}if(k==n)break;}if(k==n)printf("Yes!\n");else printf("No!\n");}return 0;}