POJ-3304 Segments

题意：给出n条线段，问是否存在一条直线使所有线段在其上的映射有至少一个共点

假设找到了这条直线，那过共点作直线的垂线必然与n条线段相交，就相当于问是否存在直线可以与所有线段相交

(n^2)枚举直线，然后(O(n))判断

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e3+100;
const double eps=1e-8;
struct Point{
	double x,y;
	Point(double xx=0,double yy=0){
		x=xx,y=yy;
	}
}s[maxn],t[maxn];
struct Vector{
	double x,y;
	Vector(double xx=0,double yy=0){
		x=xx,y=yy;
	}
};
int dcmp(double x){return fabs(x)<eps?0:(x>0?1:-1);}
Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
double operator * (Vector a,Vector b){return a.x*b.y-a.y*b.x;}
int tt,n;
/*bool segment(Point a,Point b,Point c,Point d){
	Vector x=b-a,y=d-c;
	Vector v1=c-a,v2=d-a;
	if(dcmp(x*v1)*dcmp(x*v2)>0) return 0;
	v1=a-c,v2=b-c;
	if(dcmp(y*v1)*dcmp(y*v2)>0) return 0;
	return 1;
}*/
bool check(Point x,Point y){
	if(dcmp(x.x-y.x)==0&&dcmp(x.y-y.y)==0) return 0;
	for(int i=1;i<=n;i++)
		if(((y-x)*(s[i]-x))*((y-x)*(t[i]-x))>eps)
			return 0;
	return 1;
}
int main(){
	scanf("%d",&tt);
	while(tt--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%lf%lf%lf%lf",&s[i].x,&s[i].y,&t[i].x,&t[i].y);
		bool ok=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)
				if(check(s[i],t[j])||check(s[i],s[j])||check(t[i],t[j])||check(t[i],s[j])){
					ok=1;
					break;
				}
			if(ok) break;
		}
		if(ok) printf("Yes!
");
		else printf("No!
");
	}
	return 0;
}