题目大意：给出n条线段，问是否存在一条直线，使得n条线段在直线上的投影有至少一个公共点。
题目思路:如果假设成立，那么作该直线的垂线l，该垂线l与所有线段相交，且交点可为线段中的某两个交点
证明：若有l和所有线段相交，则可保持l和所有线段相交，左右平移l到和某一线段交于端点停止（“移不动了”）。然后绕这个交点旋转。也是转到“转不动了”（和另一线段交于其一个端点）为止。这样就找到了一个新的l满足题意，而且经过其中两线段的端点。
如何判断直线是否与线段相交：如果线段的两个端点在直线的两侧，那么线段与直线相交，因此可利用叉积来经行判断。
#include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<stdio.h> #include<stdlib.h> #include<queue> #include<math.h> #include<map> #define INF 0x3f3f3f3f #define MAX 100005 #define Temp 1000000000 #define MOD 1000000007 using namespace std; int n; struct node { double x1,y1,x2,y2; }a[MAX]; int check(int pos,double x1,double y1,double x2,double y2)//求叉积 { double x3=a[pos].x1,y3=a[pos].y1,x4=a[pos].x2,y4=a[pos].y2; if(fabs(x1-x2)<1e-8 && fabs(y1-y2)<1e-8) return 0; double op1=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1); double op2=(x2-x1)*(y4-y1)-(x4-x1)*(y2-y1); if(op1*op2 > (1e-8)) return 0; return 1; } int Find(double x1,double y1,double x2,double y2) { for(int i=0;i<n;i++) { if(!check(i,x1,y1,x2,y2)) return 0; } return 1; } int solve() { for(int i=0;i<n;i++)//枚举端点 { for(int j=i+1;j<n;j++) { if(Find(a[i].x1,a[i].y1,a[i].x2,a[i].y2))//上方线段 return 1; if(Find(a[i].x1,a[i].y1,a[j].x1,a[j].y1))//两条线段左端连线 return 1; if(Find(a[i].x1,a[i].y1,a[j].x2,a[j].y2))//两条线段左上右下连线 return 1; if(Find(a[i].x2,a[i].y2,a[j].x1,a[j].y1))//两条线段右上左下连线 return 1; if(Find(a[j].x1,a[j].y1,a[j].x2,a[j].y2))//下方线段 return 1; if(Find(a[i].x2,a[i].y2,a[j].x2,a[j].y2))//两条线段有段连线 return 1; } } return 0; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2); } if(n<3)//如果有一个或两个线段特判一下 { printf("Yes! "); continue; } int ok=solve(); if(ok) printf("Yes! "); else printf("No! "); } return 0; }