首页 > 代码库 > Segment

Segment

2024-07-31 05:58:05   216人阅读

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 integern ≤ 100 showing the number of segments. After that, n lines containing four real numbersx1y1x2y2 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 numbersa 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!
# include <iostream>
# include <cmath>
# include <cstdio>
using namespace std;

# define EPS 1e-8

int n;

struct Segment
{
    double x1,x2,y1,y2;
}segment[1000];

double distance(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

double fun(double x1,double y1,double x2,double y2,double x0,double y0)
{
    return  (x2-x1)*(y0-y1)-(x0-x1)*(y2-y1);
}

bool search(double x1,double y1,double x2,double y2)
{
    int i;
    //判断是不是同一条直线;
    if(distance(x1,y1,x2,y2)<EPS)    return false;
    //利用叉积定理，判断是不是和其他的线段相交：
    for(i=0;i<n;i++)
    {
        if(fun(x1,y1,x2,y2,segment[i].x1,segment[i].y1)*
           fun(x1,y1,x2,y2,segment[i].x2,segment[i].y2)>EPS)    return false;
    }
    return true;
}

int main ()
{
    //freopen("a.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int i;
        for(i=0;i<n;i++)
            scanf("%lf%lf%lf%lf",&segment[i].x1,&segment[i].y1,&segment[i].x2,&segment[i].y2);
        if(n==1)    { printf("Yes!\n"); continue;}

        int ans=0;
        
        //将所有的线段都列举出来；
        for(i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
        {
            if(search(segment[i].x1,segment[i].y1,segment[j].x1,segment[j].y1)||
               search(segment[i].x1,segment[i].y1,segment[j].x2,segment[j].y2)||
               search(segment[i].x2,segment[i].y2,segment[j].x1,segment[j].y1)||
               search(segment[i].x2,segment[i].y2,segment[j].x2,segment[j].y2))
                ans=1;
        }
        if(ans)    printf("Yes!\n");
        else    printf("No!\n");
    }
    return 0;
}


Segment


联系
我们