POJ3304 (Segments)[计算几何]

发表于 | 更新于 | | 阅读次数：

题目链接：http://poj.org/problem?id=3304

题目大意：二维平面上n个线段，问是否存在一条直线，使得所有线段垂直投射到该直线上的投影，都两两有公共点？

所有投影都两两有公共点，那么投影直线一定有一条法线穿过所有的线段，问题转化为是否存在一条直线穿过所有的线段。
通过旋转平移的方式我们一定可以让这条直线经过所有线段中的至少两个端点（想象如果没有经过，那么我们把它向外移直到「撞到」一个端点，再通过旋转的方式使它再「撞」到另一个端点）。
因此枚举两个端点，并判断经过两端点的直线是否经过所有的线段即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1e-8;
const double inf=1e20;
const int maxn=5009;
int sgn(double x) {
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    else return 1;
}
inline double sqr(double x) { return x*x; }
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
        x=_x;
        y=_y;
    }
    double operator ^(const Point &b) const {
        return x*b.y-y*b.x;
    }
    Point operator -(const Point &b) const {
        return Point(x-b.x,y-b.y);
    }
    bool operator ==(Point b) const {
        return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
    }
}points[maxn*2];
struct Line {
    Point s,e;
    Line() {}
    Line(Point _s,Point _e) {
        s=_s;
        e=_e;
    }
    int relation(Point p) {
        int c=sgn((p-s)^(e-s));
        if(c<0) return 1;
        else if(c>0) return 2;
        else return 3;
    }
    int linecrossseg(Line v) {
        int d1=sgn((e-s)^(v.s-s));
        int d2=sgn((e-s)^(v.e-s));
        if((d1^d2)==-2) return 2;
        return (d1==0 || d2==0);
    }
}lines[maxn];
int main() {
    int T;
    int m,n;
    double x1,y1,x2,y2;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&m);
        n=0;
        for(int i=1;i<=m;i++) {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            points[++n]=Point(x1,y1);
            points[++n]=Point(x2,y2);
            lines[i]=Line(points[n-1],points[n]);
        }
        bool flag=0;
        bool found=0;
        for(int i=1;i<=n && !found;i++) {
            for(int j=1;j<=n && !found;j++) {
                flag=0;
                if(i!=j && !(points[i]==points[j])) {
                    flag=1;
                    for(int k=1;k<=m;k++) if(!Line(points[i],points[j]).linecrossseg(lines[k])) {
                        flag=0;
                        break;
                    }
                }
                if(flag) {
                    found=1;
                    break;
                }
            }
        }
        puts(found ? "Yes!" : "No!");
    }
}