题意简述
多测，每次给定\(n\)条线段，请问是否能找到\(1\)条直线，使得所有线段在该直线上的投影有公共部分。
注：两点距离\(<10^{-8}\)被认为是相等的。
思路分析
题意转化一下，就是要我们找一条直线\(l_1\)，穿过所有线段。这样对于任意直线\(l_2\perp l_1\)，都满足题意。
我们又发现，如果存在\(l_2\)，那么在规定“\(l_2\)必须穿过所有端点中的至少\(2\)个”的前提下，\(l_2\)仍然存在。
为什么呢？
比如这条红色直线就是我们找到的答案。
接下来将红色直线左移，直到“再移一下就不能穿过所有线段”为止。显然此时一定有一个端点在直线上。
绕这个端点旋转红色直线，直到“再旋转一下就不能穿过所有线段”位置。显然此时直线上又多了一个端点。而同时满足题目要求。
接下来枚举两两线段之间的端点，判断过这两个端点的直线是否穿过所有线段即可。
判断线段穿过直线仅需一次跨立实验。即：
- 设有线段\(AB\)，直线\(CD\)。
- 则如果\(\vec{AC}\)与\(\vec{AD}\)的方向关系和\(\vec{BC}\)与\(\vec{BD}\)的方向关系不同，则说明\(AB\)与\(CD\)相交。否则不相交。判断两向量方向关系需要用到叉积，具体可以见[题解]UVA10902 Pick-up Sticks中对跨立实验的说明。
我们可以发现，答案如果存在，则选择的两个端点一定可以不在一条线段上。所以枚举线段时\(j\)可以从\(i+1\)开始，但相应地需要特判一下\(n=1\)的情况，直接输出Yes即可。
另外，枚举出的两个端点如果重合（即距离\(<10^{-8}\)）则不应参与计算。
时间复杂度\(O(n^3)\)。
Code
POJ真的是时代的眼泪了……编译器太老了，代码需要很多修改，因此就不放修改后的较为冗长的代码了。
重在理解，所以放一份修改前、比较简洁的代码实现，注意无法通过POJ编译。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
struct point{double x,y;};
struct segment{point a,b;};
struct line{point a,b;};
double cross(point a,point b){return a.x*b.y-b.x*a.y;}
point vec(point a,point b){return {b.x-a.x,b.y-a.y};}
double dist(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
bool intersect_line(line a,segment b){
return cross(vec(b.a,a.a),vec(b.a,a.b))*cross(vec(b.b,a.a),vec(b.b,a.b))<=0;
}
int t,n;
segment ts[110];
bool solve(line a){
if(dist(a.a,a.b)<1e-8) return 0;
for(int i=1;i<=n;i++)
if(!intersect_line(a,ts[i])) return 0;
return 1;
}
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)
cin>>ts[i].a.x>>ts[i].a.y>>ts[i].b.x>>ts[i].b.y;
bool f=0;
if(n==1) f=1;
else{
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if(solve({ts[i].a,ts[j].a})||solve({ts[i].a,ts[j].b})||
solve({ts[i].b,ts[j].a})||solve({ts[i].b,ts[j].b})){f=1;break;}
}
}
}
if(f) cout<<"Yes!\n";
else cout<<"No!\n";
}
}