題目大意：給出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 1000000007using 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!\n");continue;}int ok=solve();if(ok)printf("Yes!\n");elseprintf("No!\n");}return 0; }
?
