首页 > 代码库 > Segments

Segments

2024-10-27 02:19:01   209人阅读

Segments

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 x1y1 x2 y2 follow, in which (x1, y1) and (x2, y2) 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个点叠在一起的。如果我们把它展开了，以另一个视角观察将会是这样的：

技术分享

 

所有线段在直线ansL上都会有一个共同的投影点，A。再观察，发现那些投影到A点的点都被直线L所经过。所以，题目就变成了，判断是否存在一条直线，与所有线段相交。

在实际操作时，只需枚举2n个点中任意两个点，判断经过这两点的直线是否符合要求。

技术分享 
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 const double eps=1e-8;
 7 int n;
 8 struct point{double x,y;}u[105],v[105];
 9 point operator - (point P,point Q){point ret; ret.x=P.x-Q.x,ret.y=P.y-Q.y; return ret;}
10 double cross(point P,point Q){return P.x*Q.y-Q.x*P.y;}
11 bool jug(point P,point Q){
12     if (fabs(P.x-Q.x)<eps&&fabs(P.y-P.y)<eps) return 0;
13     for (int i=0; i<n; i++) if (cross(P-u[i],Q-u[i])*cross(P-v[i],Q-v[i])>eps) return 0;
14     return 1;
15 }
16 int main(){
17     int T;
18     for (scanf("%d",&T); T; T--){
19         scanf("%d",&n);
20         for(int i=0; i<n; i++) scanf("%lf%lf%lf%lf",&u[i].x,&u[i].y,&v[i].x,&v[i].y);
21         bool flag=0; if (n<3) flag=1;
22         for(int i=0; i<n-1; i++) if (!flag)
23             for(int j=i+1; j<n; j++) if (!flag)
24             if(jug(u[i],u[j])||jug(u[i],v[j])||jug(v[i],u[j])||jug(v[i],v[j])) flag=true;
25         printf("%s\n",flag?"Yes!":"No!");
26     }
27     return 0;
28 }
View Code

 

Segments


联系
我们