POJ 3304 Segments（计算几何）

Segments
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 12916 Accepted: 4111
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!
Source

Amirkabir University of Technology Local Contest 2006

---

思路：
1、题目大意是 在一个二维空间内给你一些线段的始末坐标点，如果存在一个直线，如果所有线段在直线上的投影至少有一个公共点输出Yes!否则No!

2、对两个线段来说，如果有一条直线L与这两个线段相交，直线M与L垂直，那么直线L与 两个线段的交点投影在直线M上，我们发现投影到直线M上的这个点为两线段投影在直线M上的一个公共点，与题目要求的相符合。

3、所以现在问题变成了：如果存在一条直线L与所有给出的线段都相交，那么所有线段投影在与L垂直的直线M上至少会有一个公共点。

---

AC代码：

#include<iostream>
#include<cmath>

using namespace std;

const int MAX = 105;
const double eps = 1e-8;
struct Point{
    double x,y;
}s[MAX],e[MAX];
int n;

double mult(Point sp,Point ep,Point op){
    return (sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y);
}

bool solve(Point p1,Point p2){
    if(abs(p1.x-p2.x)<eps && abs(p1.y-p2.y)<eps) return false;
    for(int i=0;i<n;i++)
        if(mult(p1,p2,s[i])*mult(p1,p2,e[i])>eps)   return false;
    return true;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>s[i].x>>s[i].y>>e[i].x>>e[i].y;

        bool flag=false;
        if(n<3) flag=true;

        for(int i=0; i<n && !flag ;i++){
            for(int j=i+1; j<n && !flag ;j++){
                if(solve(s[i],s[j])) flag=true;
                else if(solve(s[i],e[j])) flag=true;
                else if(solve(e[i],s[j])) flag=true;
                else if(solve(e[i],e[j])) flag=true;
            }
        }
        if(flag)    cout<<"Yes!"<<endl;
        else        cout<<"No!"<<endl;
    }
}