题目链接：https://vjudge.net/problem/POJ-3304
题意：求是否能找到一条直线，使得n条线段在该直线的投影有公共点。
思路：
如果存在这样的直线，那么在公共投影点作直线的垂线，显然该垂线会经过所有直线，那么原题转换为求是否有经过所有线段的直线。
如果存在这样的直线，那么该直线一定能通过平移和旋转之后经过所有线段中的两个端点，那么我们枚举所有两两线段的端点作为直线的两点，然后是判断直线是否经过所有线段。如果线段为p0p1，直线为p2p3，那么相交时满足：(p0p2^p0p3)*(p1p2^p1p3)<=0。总复杂度为O(n^3)。
AC code：
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std; const int maxn=;
const double eps=1e-;
int T,n,flag; struct Point{
double x,y;
Point(){}
Point(double xx,double yy):x(xx),y(yy){}
Point operator + (const Point& b)const{
return Point(x+b.x,y+b.y);
}
Point operator - (const Point& b)const{
return Point(x-b.x,y-b.y);
}
double operator * (const Point& b)const{
return x*b.x+y*b.y;
}
double operator ^ (const Point& b)const{
return x*b.y-b.x*y;
}
}; struct Line{
Point s,e;
Line(){};
Line(Point ss,Point ee){
s=ss,e=ee;
}
}line[maxn]; int sgn(double x){
if(abs(x)<eps) return ;
if(x<) return -;
return ;
} double dist(Point a,Point b){
return sqrt((b-a)*(b-a));
} double xmult(Point p0,Point p1,Point p2){ //p0p1 ^ p0p2
return (p1-p0)^(p2-p0);
} bool seg_inter_line(Line l1,Line l2){ //判断直线l1和线段l2是否相交
return sgn(xmult(l2.s,l1.s,l1.e))*sgn(xmult(l2.e,l1.s,l1.e))<=;
} bool check(Point p1,Point p2){
if(sgn(dist(p1,p2))==) return ;
Line l1=Line(p1,p2);
for(int i=;i<=n;++i)
if(!seg_inter_line(l1,line[i]))
return ;
return ;
} int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
flag=;
for(int i=;i<=n;++i){
double x1,y1,x2,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[i]=Line(Point(x1,y1),Point(x2,y2));
}
for(int i=;i<=n;++i){
for(int j=i;j<=n;++j)
if(check(line[i].s,line[j].s)||check(line[i].s,line[j].e)||
check(line[i].e,line[j].s)||check(line[i].e,line[j].e)){
flag=;
break;
}
if(flag)
break;
}
if(flag) printf("Yes!\n");
else printf("No!\n");
}
return ;
}