Segments(叉积)

Segments

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 18066		Accepted: 5680

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!

枚举每两个线段的端点，判断这些端点形成的直线是否与线段都有交点
还有，题目说如果两个点的距离小于1e-8就看成一个点，所以要考虑重点

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<string>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 using namespace std;
11 
12 struct Point{
13     double x,y;
14 };
15 
16 struct Line{
17     Point s,e;
18 }line[105];
19 
20 double Cross(double x0,double y0,double x1,double y1,double x2,double y2){
21     return (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
22 }
23 
24 
25 double distance(double x1,double y1,double x2,double y2){
26     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
27 }
28 
29 bool Check(double x1,double y1,double x2,double y2,int n){
30     if(distance(x1,y1,x2,y2)<0.00000001) return 0;
31     for(int i=1;i<=n;i++){
32         if(Cross(x1,y1,x2,y2,line[i].s.x,line[i].s.y)*Cross(x1,y1,x2,y2,line[i].e.x,line[i].e.y)>0.00000001){
33             return 0;
34         }
35     }
36     return 1;
37 }
38 
39 bool ac(int n){
40     Line tmp;
41     int co=0;
42     for(int i=1;i<=n;i++){
43         for(int j=1;j<=n;j++){
44             tmp.s=line[i].s;
45             tmp.e=line[j].s;
46             if(Check(tmp.s.x,tmp.s.y,tmp.e.x,tmp.e.y,n)){
47                 co=1;
48             }
49             tmp.s=line[i].s;
50             tmp.e=line[j].e;
51             if(Check(tmp.s.x,tmp.s.y,tmp.e.x,tmp.e.y,n)){
52                 co=1;
53             }
54             tmp.s=line[i].e;
55             tmp.e=line[j].s;
56             if(Check(tmp.s.x,tmp.s.y,tmp.e.x,tmp.e.y,n)){
57                 co=1;
58             }
59             tmp.s=line[i].e;
60             tmp.e=line[j].e;
61             if(Check(tmp.s.x,tmp.s.y,tmp.e.x,tmp.e.y,n)){
62                 co=1;
63             }
64         }
65 
66     }
67     if(co)
68         return true;
69     return false;
70 }
71 
72 int main(){
73 
74     int T;
75     cin>>T;
76     while(T--){
77         int n;
78         cin>>n;
79         Point s,e;
80         for(int i=1;i<=n;i++){
81             cin>>s.x>>s.y>>e.x>>e.y;
82             line[i].s=s;
83             line[i].e=e;
84         }
85         if(ac(n)){
86             puts("Yes!");
87         }
88         else{
89             puts("No!");
90         }
91     }
92 
93 }

View Code