poj 3304 判断是否存在一条直线与所有线段相交

Segments

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 8579		Accepted: 2608

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!

题目大意:问是否存在一条直线所有线段在它上面的投影至少有一个公共交点，等同与这条直线的垂线与所有线段都有交点。即求是否有一条与所有线段相交。两两枚举线段四个端点两两成四条直线，
若所有的线段的两个端点分别在直线的两边（只要不是在同一边就行，在直线上也可以），那么说明存在这么一条直线。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};

struct Segment{
    Point a,b;
};

typedef Point Vector;
Vector operator -(const Point &A,const Point &B){ return Vector(A.x-B.x,A.y-B.y);}
bool operator < (const Point &a,const Point &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
const double eps=1e-10;

int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    else return x<0?-1:1;
}

bool operator == (const Point &a,const Point &b){
    return (dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0);
}
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//点积
double Length(Vector A){return sqrt(Dot(A,A));}//向量长度
//两向量的夹角
double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}
double Cross(Vector A,Vector B){ return A.x*B.y-A.y*B.x;}//叉积

vector<Segment> S;

bool judge(Point a,Point b)
{
    if(a == b) return false;//a,b属于同一个点，一个点不能确定一条直线
    int i,n=S.size();
    Vector v1=b-a,v2,v3;
    for(i=0;i<n;i++)
    {
        v2=S[i].a-a;
        v3=S[i].b-a;
        if(dcmp(Cross(v1,v2)*Cross(v1,v3)) > 0) return false;
    }
    return true;
}

bool solve()
{
    int i,j,n=S.size();
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        if(judge(S[i].a,S[j].a) || judge(S[i].a,S[j].b) || judge(S[i].b,S[j].a) || judge(S[i].b,S[j].b))
              return true;
    }
    return false;
}
int main()
{
    int T,n,i;
    Segment s;
    scanf("%d",&T);
    while(T--)
    {
        S.clear();
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%lf %lf %lf %lf",&s.a.x,&s.a.y,&s.b.x,&s.b.y);
            S.push_back(s);
        }
        if(n==1) printf("Yes!
");
        else if(solve()) printf("Yes!
");
        else printf("No!
");
    }
    return 0;
}

poj 3304 判断是否存在一条直线与所有线段相交

相关推荐