计算几何中直线与线段相交的判断。主要的难点是能够想到题目可以转化成直线与线段相交的判断问题。

原题地址：http://poj.org/problem?id=3304

POJ 3304 线段

问题描述

现在平面上有若干条线段，问能不能找到一条直线，让所有线段在这条直线上的投影至少有一个公共点。

输入数据

输入数据中，第一个数 T 表示接下来有几组测试。接下来的 T 组测试数据中的每一组，第一行是一个数字 n, 表示这组数据中有几条线段，接下来的 n 行，每行有 4 个数字，表示每条线段的 (x1, y1), (x2, y2) 两个端点。

输出数据

对于每组输出数据，输出是否存在那样一条直线。若存在则输出“YES!”，否则输出“NO!”。

样例输入

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

样例输出

Yes!
Yes!
No!

解题思路

其实如果存在那么一条直线，让这么多线段在这条直线上的投影至少有一个公共点，那么如果过这些公共点中的任何一个点对这条直线做垂线，则这条垂线会与所有线段相交。反之若没有这样一条直线，也找不到一条直线与所有这些线段相交。所以问题就转化成了找一条直线与所有线段相交的问题。

但是如何找到这样一条直线呢？有一种方法是在所有线段的端点中枚举两个不同的且不重合的端点，然后判断这两个端点确定的直线是否与其余所有线段相交，若成则可输出“YES!”，若所有两个端点都被枚举还未找到，则输出“NO!”。

源代码

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
87
88
89
90
91
92
93
94
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

#define eps 1e-9
#define inf 1e9

inline int sgn(double a) {
    if (a < -eps) return -1;
    else if (a > eps) return 1;
    return 0;
}

inline bool lt(double a, double b) { return sgn(a - b) < 0; }
inline bool gt(double a, double b) { return sgn(a - b) > 0; }
inline bool eq(double a, double b) { return sgn(a - b) == 0; }

struct point {
    double x, y;
    point() : x(0.0), y(0.0) { }
    point(double _x, double _y) : x(_x), y(_y) { }
    point operator-(const point &p) const {
        return point(x - p.x, y - p.y);
    }
    double sqrmag() const { return x * x + y * y; }
    double mag() const { return sqrt(sqrmag()); }
};

inline double cross(const point &a, const point &b) {
    return a.x * b.y - b.x * a.y;
}

inline double dot(const point &a, const point &b) {
    return a.x * b.x + a.y * b.y;
}

struct line {
    point a, b;
    line() { }
    line(const point &_a, const point &_b) : a(_a), b(_b) { }
    double length() const { return (b - a).mag(); }
};

inline bool intersects(const line &l, const line &s) {
    double a = cross(s.a - l.a, l.b - l.a);
    double b = cross(s.b - l.a, l.b - l.a);
    return sgn(a * b) <= 0;
}

#define N 100

line lines[N];
size_t n;

inline bool intersects_all(const point &a, const point &b) {
    line l(a, b);
    if (!sgn(l.length()))
        return false;
    for (size_t i = 0; i < n; ++i)
        if (!intersects(l, lines[i]))
            return false;
    return true;
}

int main(int argc, char *argv[]) {
    size_t c;
    scanf("%d", &c);
    while (c--) {
        scanf("%d", &n);
        for (size_t i = 0; i < n; ++i) {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            lines[i].a.x = x1; lines[i].a.y = y1;
            lines[i].b.x = x2; lines[i].b.y = y2;
        }
        if (n == 1) goto yes;
        for (size_t i = 0; i < n; ++i) {
            for (size_t j = i + 1; j < n; ++j) {
                line l1(lines[i].a, lines[j].a);
                if (intersects_all(lines[i].a, lines[j].a)) goto yes;
                if (intersects_all(lines[i].a, lines[j].b)) goto yes;
                if (intersects_all(lines[i].b, lines[j].a)) goto yes;
                if (intersects_all(lines[i].b, lines[j].b)) goto yes;
            }
        }
        printf("No!\n"); continue;
        yes: printf("Yes!\n");
    }
    return EXIT_SUCCESS;
}

原创文章，转载请注明来源：http://euyuil.com/2405/poj-3304-segments/