poj 3304 Segments（计算直线与线段之间的关系）

Segments

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 10921 Accepted: 3422

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

题意：t组数据，每组n个线段，都是给定四个点表,问是否存在一条直线使所有线段在这个直线上的投影互相至少相交于一点.

思路：转化成存在一条直线与所有线段都相交。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <math.h>
 7 #include <algorithm>
 8 #include <cctype>
 9 #include <string>
10 #include <map>
11 #include <set>
12 #define ll long long
13 using namespace std;
14 const double eps = 1e-8;
15 int sgn(double x)
16 {
17     if(fabs(x) < eps)return 0;
18     if(x < 0) return -1;
19     else return 1;
20 }
21 struct Point
22 {
23     double x,y;
24     Point(){}
25     Point(double _x,double _y)
26     {
27         x = _x;y = _y;
28     }
29     Point operator -(const Point &b)const
30     {
31         return Point(x - b.x,y - b.y);
32     }
33     double operator ^(const Point &b)const
34     {
35         return x*b.y - y*b.x;
36     }
37     double operator *(const Point &b)const
38     {
39         return x*b.x + y*b.y;
40     }
41 };
42 struct Line
43 {
44     Point s,e;
45     Line(){}
46     Line(Point _s,Point _e)
47     {
48         s = _s;e = _e;
49     }
50 };
51 double xmult(Point p0,Point p1,Point p2) //p0p1 X p0p2
52 {
53     return (p1-p0)^(p2-p0);
54 }
55 bool Seg_inter_line(Line l1,Line l2) //判断直线l1和线段l2是否相交
56 {
57     return sgn(xmult(l2.s,l1.s,l1.e))*sgn(xmult(l2.e,l1.s,l1.e)) <= 0;
58 }
59 double dist(Point a,Point b)
60 {
61     return sqrt( (b - a)*(b - a) );
62 }
63 const int MAXN = 105;
64 Line line[MAXN];
65 bool check(Line l1,int n)
66 {
67     if(sgn(dist(l1.s,l1.e)) == 0) return false;
68     for(int i = 0 ; i < n; i++)
69         if(Seg_inter_line(l1,line[i]) == false) return false;
70     return true;
71 }
72 
73 int main(void)
74 {
75     int n,t;
76     scanf("%d",&t);
77     while(t--)
78     {
79         scanf("%d",&n);
80         double x1,y1,x2,y2;
81         for(int i = 0; i < n; i++)
82         {
83             scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
84             line[i] = Line(Point(x1,y1),Point(x2,y2));
85         }
86         bool flag = false;
87         for(int i = 0; i < n; i++)
88             for(int j = 0; j < n; j++)
89             if(check(Line(line[i].s,line[j].s),n)  ||   check(Line(line[i].s,line[j].e),n) || check(Line(line[i].e,line[j].s),n)||check(Line(line[i].e,line[j].e),n) )
90             {
91                 flag = true;
92                 break;
93             }
94 
95         if(flag) printf("Yes!
");
96         else printf("No!
");
97     }
98     return 0;
99 }

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 10921		Accepted: 3422