【POJ 3304】Segments

【题目】

传送门

Description

Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common.

Input

Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing a positive integer n ≤ 100 showing the number of segments. After that, n lines containing four real numbers x1 y1 x2 y2 follow, in which (x1, y1) and (x2, y2) are the coordinates of the two endpoints for one of the segments.

Output

For each test case, your program must output “Yes!”, if a line with desired property exists and must output “No!” otherwise. You must assume that two floating point numbers a and b are equal if |a - b| < 10-8.

Sample Input

3
2
1.0 2.0 3.0 4.0
4.0 5.0 6.0 7.0
3
0.0 0.0 0.0 1.0
0.0 1.0 0.0 2.0
1.0 1.0 2.0 1.0
3
0.0 0.0 0.0 1.0
0.0 2.0 0.0 3.0
1.0 1.0 2.0 1.0

Sample Output

Yes!
Yes!
No!

【分析】

大致题意：给出 $n$n 条线段，问是否存在一条直线，使得所有的线段投影到它上面后，至少有一个公共交点

转换一下题意，假设所有的存在这样的直线，那么在公共部分做一条垂线，必然能经过所有线段，所以原问题就可以转换为是否存在一条直线，使它能经过所有线段

可以发现，如果存在这样的直线，那么它必然可以恰好经过两条线段的端点（就是理解成这条线可以在允许的范围内旋转，而这两个端点恰好卡住了这条线）

因此枚举这两个端点，然后暴力枚举求解即可

【代码】

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 105
#define eps 1e-8
using namespace std;
int n;
struct point
{
	double x,y;
	point(){}
	point(double x,double y):x(x),y(y){}
	point operator+(const point &a)  {return point(x+a.x,y+a.y);}
	point operator-(const point &a)  {return point(x-a.x,y-a.y);}
	friend double dot(const point &a,const point &b)  {return a.x*b.x+a.y*b.y;}
	friend double cross(const point &a,const point &b)  {return a.x*b.y-b.x*a.y;}
	friend double dist(const point &a,const point &b)  {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
};
struct line
{
	point s,t;
	line(){}
	line(point s,point t):s(s),t(t){}
}l[N];
int sign(double x)
{
	if(fabs(x)<eps)  return 0;
	if(x<0)  return -1;
	return 1;
}
bool intersect(line a,line b)
{
	return sign(cross(b.s-a.s,b.s-a.t)*cross(b.t-a.s,b.t-a.t))<=0;
}
bool check(line L)
{
	if(sign(dist(L.s,L.t))==0)
	  return false;
	for(int i=1;i<=n;++i)
	  if(!intersect(L,l[i]))
	    return false;
	return true;
}
int main()
{
	int i,j,t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(i=1;i<=n;++i)
		  scanf("%lf%lf%lf%lf",&l[i].s.x,&l[i].s.y,&l[i].t.x,&l[i].t.y);
		bool flag=false;
		if(n==1)  flag=true;
		for(i=1;i<=n;++i)
		  if(check(l[i]))
		    flag=true;
		for(i=1;i<=n;++i)
		{
			for(j=i+1;j<=n;++j)
			{
				if(check(line(l[i].s,l[j].s)))  flag=true;
				if(check(line(l[i].s,l[j].t)))  flag=true;
				if(check(line(l[i].t,l[j].s)))  flag=true;
				if(check(line(l[i].t,l[j].t)))  flag=true;
				if(flag)  break;
			}
			if(flag)  break;
		}
		puts(flag?"Yes!":"No!");
	}
	return 0;
}