POJ 3304 计算几何

Segments

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 3703		Accepted: 1026

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 x₁y₁x₂y₂ follow, in which (x₁, y₁) and (x₂, y₂) 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!

Source

Amirkabir University of Technology Local Contest 2006

这个题题意是：

求是否存在一条直线，使所有线段到这条直线的投影至少有一个交点

这个题目可以转化为是否有一条直线可以与所有的线段相交

简单证明一下：

如果存在一条直线可以满足题意，那么必然这条直线的垂线就一定可以与点集中任意两点连起来的那个线段相交，而且我们可以通过旋转这条直线让他和某一条线段重合

于是解题思路就变成了：

二重循环枚举端点，并且用这两个端点构成一条直线，并判断这条直线是不是可以与所有的线段相交

我的代码：

代码很快就敲出来了，不过一直得不到正确答案，调试了很久才发现我数组的下标全部是从1开始的，所以判断直线和线段相交的时候要写成if(k==n+1)先开始写成k==n了。。。

Source Code

Problem: 3304		User: bingshen
Memory: 200K		Time: 32MS
Language: C++		Result: Accepted

• Source Code

  #include<stdio.h>
  #include<math.h>
  #define eps 1e-8
  
  struct point
  {
  	double x;
  	double y;
  };
  struct line
  {
  	point a;
  	point b;
  };
  
  point p[205];
  line l[105];
  
  double dis(point a,point b)
  {
  	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
  }
  
  double cross(point p1,point p2,point p0)
  {
  	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
  }
  
  bool work(int n)
  {
  	int i,j,k;
  	for(i=1;i<=2*n;i++)
  	{
  		for(j=i+1;j<=2*n;j++)
  		{
  			if(dis(p[i],p[j])<=eps)
  				continue;
  			for(k=1;k<=n;k++)
  				if(cross(l[k].a,p[i],p[j])*cross(l[k].b,p[i],p[j])>0)
  					break;
  			if(k==n+1)
  				return true;
  		}
  	}
  	return false;
  }
  
  int main()
  {
  	int i,n,t;
  	double x,y;
  	scanf("%d",&t);
  	while(t--)
  	{
  		scanf("%d",&n);
  		for(i=1;i<=n;i++)
  		{
  			scanf("%lf%lf",&x,&y);
  			p[2*i-1].x=x;
  			p[2*i-1].y=y;
  			scanf("%lf%lf",&x,&y);
  			p[2*i].x=x;
  			p[2*i].y=y;
  			l[i].a=p[2*i-1];
  			l[i].b=p[2*i];
  		}
  		if(work(n))
  			printf("Yes!/n");
  		else
  			printf("No!/n");
  	}
  	return 0;
  }
  
  

没有天分，只有勤奋~~