题意：判断是否存在一条直线与所有线段相交
思路：枚举线段端点
#include <iostream> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <cstdio> using namespace std; #define eps 1e-8 struct point { double x,y; point() { } point(double xx,double yy) { x=xx; y=yy; } } p[500]; int judge(int a,int b) { if(a%2==1) a--; if(a==b) return 1; return 0; } int banana(point a,point b,point c,point d) { double cd=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); double dd=(b.x-a.x)*(d.y-a.y)-(d.x-a.x)*(b.y-a.y); if(fabs(cd)<eps) return 1; if(fabs(dd)<eps) return 1; if(cd*dd<=eps) return 1; return 0; } double dist(int a,int b) { return hypot(fabs(p[a].x-p[b].x),fabs(p[a].y-p[b].y)); } int main() { int T,n,i,j,k; scanf("%d",&T); while(T--) { scanf("%d",&n); n*=2; for(i=0; i<n; i+=2) { scanf("%lf%lf",&p[i].x,&p[i].y); scanf("%lf%lf",&p[i+1].x,&p[i+1].y); } int flag=0; for(i=0; i<n; i++) { for(j=i+1; j<n; j++) { if(judge(j,i)) continue; if(dist(i,j)<eps) continue; flag=0; for(k=0; k<n; k+=2) { if(judge(i,k)) continue; if(judge(j,k)) continue; if(banana(p[i],p[j],p[k],p[k+1])==0) { flag=1; break; } } if(flag==0) break; } if(flag==0) break; } if(flag==0) printf("Yes! "); else printf("No! "); } return 0; }