首页 > 代码库 > [POJ 3304]Segments

[POJ 3304]Segments

2024-11-13 15:32:39   203人阅读

Segments

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 14918   Accepted: 4728

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 x1 y1 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条线段两个端点的坐标，问所有线段投影到一条直线上,




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


题解：


首先转化题意，把问题转化为是否存在一条直线与每条线段都有交点。


然后两两枚举线段，每对线段可以产生四条直线，再分别判断是否可以经过所有线段即可。


以上题意转化证明：大佬的博客


本题需要计算几何的相关知识，具体来说应该是跨立实验判断直线与线段有无交点。


特别注意：


1.精度问题，小于精度就直接判断为相等，特别地，两个点距离小于精度的判断为同一个点，此时不能确定一条直线。


2.所得直线有可能和某一条线段重合，所以不能加i!=j的判断。


以下是AC代码：


 




#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstring>
#include<cstdlib>
#define exp (1e-8)
using namespace std;
int t,n;
struct Vector
{
    double x,y;
    Vector(){}
    Vector(int xx,int yy){x=xx;y=yy;}
    Vector operator+(Vector b)
    {
        Vector ans;
        ans.x=x+b.x;ans.y=y+b.y;
        return ans;
    }
    Vector operator-(Vector b)
    {
        Vector ans;
        ans.x=x-b.x;ans.y=y-b.y;
        return ans;
    }
    double operator*(Vector b)
    {
        return x*b.y-b.x*y;
    }
    double operator^(Vector b)
    {
        return x*b.x+y*b.y;
    }
};
struct node
{
    Vector a,b;
}a[101];
bool find(Vector s1,Vector s2)
{
    if(fabs(s1.x-s2.x)<exp&&fabs(s1.y-s2.y)<exp)return false;
    int i,cnt=0;
    for(i=1;i<=n;i++)
    {
        if(((s1-s2)*(a[i].a-s2))*((s1-s2)*(a[i].b-s2))>exp)return false;
    }
    return true;
}
bool check(int x,int y)
{
    bool b=0;
    b|=find(a[x].a,a[y].a);
    b|=find(a[x].a,a[y].b);
    b|=find(a[x].b,a[y].a);
    b|=find(a[x].b,a[y].b);
    return b;
}
int main()
{
    int i,j;
    bool ok=0;
    scanf("%d",&t);
    while(t--)
    {
        ok=0;
        scanf("%d",&n);
        for(i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&a[i].a.x,&a[i].a.y,&a[i].b.x,&a[i].b.y);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(check(i,j))ok=1;
            }
        }
        if(ok)printf("Yes!\n");
        else printf("No!\n");
    }
}




 
[POJ 3304]Segments






























        

            
                
                  
                
                

                    联系

                    我们