poj 3304 Segments

Segments

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 14805		Accepted: 4699

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!

Source

Amirkabir University of Technology Local Contest 2006

题意：给n条线段，求是否存在某一条直线使得所有线段在这条直线上的射影有公共点

其实就是求是否存在一条直线经过所有线段，详情可见：http://blog.sina.com.cn/s/blog_6635898a0100n2lv.html，证明直线经过线段只需证明两端点对直线的叉乘小于0即可，遍历所有端点构成的直线即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<cmath>
#include<vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

#define pi acos(-1.0)
#define eps 1e-8//精度要求
#define pf printf
#define sf scanf
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define e tree[rt]
#define _s second
#define _f first
#define all(x) (x).begin,(x).end
#define mem(i,a) memset(i,a,sizeof i)
#define for0(i,a) for(int (i)=0;(i)<(a);(i)++)
#define for1(i,a) for(int (i)=1;(i)<=(a);(i)++)
#define mi ((l+r)>>1)
#define sqr(x) ((x)*(x))

const int inf=0x3f3f3f3f;
int t,m,n;

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

struct Line
{
    Point a,b;
}l[110];

double multi(Point a,Point b,Point c)
{
    return (a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x);//叉乘判断位置
}

bool check(Point a,Point b)//判断传的参数即为要构成直线的两个端点
{
    if(fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps)return 0;//两个点重合
    for0(i,m)//判断所有线段是否满足在直线两侧
        if(multi(l[i].a,a,b)*multi(l[i].b,a,b)>eps)return 0;
    return 1;
}

int main()
{
    sf("%d",&t);
    while(t--)
    {
        sf("%d",&m);
        for0(i,m)
            sf("%lf%lf%lf%lf",&l[i].a.x,&l[i].a.y,&l[i].b.x,&l[i].b.y);
        int flag=false;
        for0(i,m)//遍历所有直线
        {
            if(check(l[i].a,l[i].b))flag=1;
            for(int j=i+1;j<m;j++)
                if(check(l[i].a,l[j].a)||check(l[i].a,l[j].b)||check(l[i].b,l[j].a)||check(l[i].b,l[j].b))
                    flag=1;
        }
        puts(flag?"Yes!":"No!");
    }
    return 0;
}