poj 3304 Segments-直线跟线段相交

poj 3304 Segments--直线和线段相交

/*
题意：给一些线段  问你是否存在这样一条直线：所有这些线段在直线上的投影有公共点

假设存在  那么过这个点，做这条直线的垂线，这条垂线过所有线段
因为所有线段的投影都覆盖这点，因为他们的投影有这个公共点么

所以就是找一条直线穿过所有线段

所以枚举任意两个点组成的直线  看是否满足要求
*/
#include<stdio.h>
#include<math.h>
const double zero=1e-8;
struct point
{
	double x,y;
};
struct segment//线段
{
	point p1,p2;
}s[110];
point pp[210];//村所有的点
int t,n;
int equal(point p1,point p2)//判断是否是同一个点
{
	if(fabs(p1.x-p2.x)<=zero&&fabs(p1.y-p2.y)<=zero)
		return 1;
	return 0;
}
double cross(point p,point v1,point v2)//做叉积
{
	return (v2.x-v1.x)*(p.y-v1.y)-(p.x-v1.x)*(v2.y-v1.y);
}
int sCrossL(point s1,point s2,point l1,point l2)//判断直线是否穿过线段
{
	if(cross(s1,l1,l2)*cross(s2,l1,l2)<=0)
		return 1;
	return 0;
}
int main()
{
	int i,j,k;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(i=0;i<n;++i)
		{
			scanf("%lf%lf%lf%lf",&s[i].p1.x,&s[i].p1.y,&s[i].p2.x,&s[i].p2.y);
			pp[i*2+0].x=s[i].p1.x;
			pp[i*2+0].y=s[i].p1.y;
			pp[i*2+1].x=s[i].p2.x;
			pp[i*2+1].y=s[i].p2.y;
		}
		for(i=0;i<2*n-1;i++)
		{
			for(j=i+1;j<2*n;++j)//枚举点
			{
				if(!equal(pp[i],pp[j]))//不是同一个点
				{
					for(k=0;k<n;k++)//测试所有的边
						if(!sCrossL(s[k].p1,s[k].p2,pp[i],pp[j]))
							break;
					if(k==n)
						break;
				}
			}
			if(k==n)
				break;
		}
		if(k==n)
			printf("Yes!\n");
		else printf("No!\n");
	}
	return 0;
}