POJ 3304(线段与直线相交)

内容目录
Language:
Segments
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 7144   Accepted: 2135

Description

在平面内给 n 条线段,问是否存在一条直线,使得所有线段在这条直线上的投影有公共点.

Input

第一行输入 T 表示数据组数,接下来 T 组数据每组第一行一个整数 n ≤ 100 表示线段数,接下来n 行每行有 x1 y1 x2 y2 表示线段的两个端点 (x1y1) 和 (x2y2)
.

Output

对于每组数据,如果存在这样的直线,输出一行 "Yes!", 否则输出 "No!" . 精度|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!

Source


显然该题可转换为是否存在一条直线与所有线段相交。(如果存在,则通过移动选转,使其过的2个线段的端点)

需要特判2个点如果相同,那么连不成线段,因为最后叉积算出来为0.


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define eps 1e-8
#define MAXN (200+10)
struct P
{
	long double x,y;
	P(){}
	P(long double _x,long double _y):x(_x),y(_y){}
}a[MAXN*2];
struct V
{
	long double x,y;
	V(){}
	V(long double _x,long double _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
};
struct S
{
	P A,B;
	S(P _A,P _B):A(_A),B(_B){}
	S(){}
};
double operator*(V a,V b)
{
	return a.x*b.y-b.x*a.y;
}
bool corr(P A,P B,P C,P D)
{
	V AB=V(A,B),AC=V(A,C),AD=V(A,D);
	return ((AC*AB)*(AB*AD)>-eps);
}
bool fabs (double a,double b)
{
	if (abs(a-b)<eps) return 1 ;return 0;
}
bool fabs(P A,P B)
{
	return (fabs(A.x,B.x)&&fabs(A.y,B.y));
}
int t,n;
int main()
{
//	freopen("poj3304.in","r",stdin);
	scanf("%d",&t);
	while (t--)
	{
		cin>>n;
		bool flag=0;
		for (int i=1;i<=2*n;i++) cin>>a[i].x>>a[i].y;
		for (int i=1;i<2*n&&!flag;i++)
		{
			for (int j=i+1;j<=2*n;j++)
			{
				if (fabs(a[i],a[j])) continue;
				S l=S(a[i],a[j]);
				int k;
				for (k=1;k<=n;k++)
				{
					if (!corr(l.A,l.B,a[k*2-1],a[k*2])) break;
				//	cout<<k;
				}
				if (k==n+1) {cout<<"Yes!n"; flag=1;break;}
			}
		}

		if (!flag) cout<<"No!n";


	}
	return 0;
}