[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 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!

题目大意

给出n条线段两个端点的坐标，问所有线段投影到一条直线上,

如果这些所有投影至少相交于一点就输出Yes！，否则输出No！。

题解

计算几何。这道题要思考到两点：
1：把问题转化为是否存在一条直线与每条线段都有交点。证明：若存在一条直线$l$和所有线段相交，作一条直线$m$和$l$垂直，则$m$就是题中要求的直线，所有线段投影的一个公共点即为垂足。
2：枚举两两线段的各一个端点，连一条直线，再判断剩下的线段是否都和这条直线有交点。证明：若有$l$和所有线段相交，则可保持l和所有线段相交，左右平移$l$到和某一线段交于端点停止（“移不动了”）。然后绕这个交点旋转。也是转到“转不动了”（和另一线段交于其一个端点）为止。这样就找到了一个新的$l$满足题意，而且经过其中两线段的端点。
所以只需枚举线段的端点（注意题意，端点判重），对于枚举的这两个端点确定的直线，我们再枚举所有线段。用叉积判断枚举的线段是否分居直线两侧。

具体如何判断这里不讲了（可以看之前发过的某篇博客和另外一篇博客）

注意精度！！！

 1 #include<set>
 2 #include<map>
 3 #include<ctime>
 4 #include<cmath>
 5 #include<queue>
 6 #include<stack>
 7 #include<cstdio>
 8 #include<string>
 9 #include<vector>
10 #include<cstring>
11 #include<cstdlib>
12 #include<iostream>
13 #include<algorithm>
14 #define LL long long
15 #define RE register
16 #define IL inline
17 using namespace std;
18 const int N=100;
19 const double EXP=1e-8;
20 
21 int t,n;
22 struct Point
23 {
24     double x,y;
25     Point (){}
26     Point (double _x,double _y){x=_x;y=_y;}
27     Point operator - (const Point &b)
28     const{
29         return Point(x-b.x,y-b.y);
30     }
31     double operator * (const Point &b)
32     const{
33         return x*b.y-y*b.x;
34     }
35 };
36 struct Segment
37 {
38     Point a,b;
39 }segment[N+5];
40 
41 IL bool judge(Point a,Point b)
42 {
43     if (fabs(a.x-b.x)<EXP&&fabs(a.y-b.y)<EXP) return 0;
44     for (RE int i=1;i<=n;i++)
45         if (((a-b)*(segment[i].a-b))*((a-b)*(segment[i].b-b))>EXP) return 0;
46     return 1;
47 }
48 
49 int main()
50 {
51     scanf("%d",&t);
52     while (t--)
53     {
54         scanf("%d",&n);
55         for (RE int i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&segment[i].a.x,&segment[i].a.y,&segment[i].b.x,&segment[i].b.y);
56         bool flag=0;
57         if (n<=2) flag=1;
58         for (RE int i=1;i<=n&&!flag;i++)
59             for  (RE int j=i+1;j<=n&&!flag;j++)
60                 if (judge(segment[i].a,segment[j].a)||
61                     judge(segment[i].a,segment[j].b)||
62                     judge(segment[i].b,segment[j].a)||
63                     judge(segment[i].b,segment[j].b))
64                 flag=1;
65         printf(flag ? "Yes!
":"No!
");
66     }
67     return 0;
68 }