我们可以用蹩脚的画图法发现，如果这些线段满足投影到直线上右交点的话，那么在交点的区间做垂线是经过所有线段的，所以问题就变成了求是不是存在一条直线过所有的线段了。
那么再猜一下，这条直线肯定通过平移，旋转之类的操作过2条线段的端点，所以就可以枚举端点了。。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #define N 1000005 5 #define LL long long 6 #define inf 0x3f3f3f3f 7 #define eps 1e-8 8 using namespace std; 9 inline int ra() 10 { 11 int x=0,f=1; char ch=getchar(); 12 while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} 13 while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} 14 return x*f; 15 } 16 int T,n; 17 bool flag; 18 struct point{double x,y;}; 19 struct seg{point a,b;}s[105]; 20 point sub(point a, point b) //b->a 21 { 22 point t; t.x=a.x-b.x; t.y=a.y-b.y; return t; 23 } 24 double cross(point a, point b) 25 { 26 return a.x*b.y-a.y*b.x; 27 } 28 double turn(point p1, point p2, point p3) 29 { 30 return cross(sub(p2,p1),sub(p3,p1)); 31 } 32 bool sgn(double x, double y) 33 { 34 if (fabs(x-y)<eps) return 0; else return 1; 35 } 36 bool jud(point a, point b) 37 { 38 if (sgn(a.x,b.x)==0 && sgn(a.y,b.y)==0) return 0; 39 for (int i=1; i<=n; i++) 40 if (turn(a,b,s[i].a)*turn(a,b,s[i].b)>eps) return 0; 41 return 1; 42 } 43 int main() 44 { 45 T=ra(); 46 while (T--) 47 { 48 n=ra(); 49 for (int i=1; i<=n; i++) scanf("%lf%lf%lf%lf",&s[i].a.x,&s[i].a.y,&s[i].b.x,&s[i].b.y); 50 flag=0; 51 for (int i=1; i<=n; i++) 52 if (!flag) 53 for (int j=1; j<=n; j++) 54 { 55 if (jud(s[i].a,s[j].a) || jud(s[i].a,s[j].b) || jud(s[i].b,s[j].a) || jud(s[i].b,s[j].b)) 56 { 57 flag=1; 58 break; 59 } 60 } 61 if (!flag) printf("No! "); 62 else puts("Yes!"); 63 } 64 return 0; 65 }