很基础的直线相交问题，判断两条直线的位置关系，如果相交则求交点。

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

POJ 1269 相交的直线

题目描述

题目需要我们求若干对直线的位置关系，如果规范相交则求交点，如果不是规范相交，则判断是平行还是重合。

输入数据

输入数据的第一行表明有多少对直线，从第二行开始，每行有 8 个数字 x1 y1 x2 y2 x3 y3 x4 y4, 表示一对直线 (x1, y1) ~ (x2, y2), (x3, y3) ~ (x4, y4).

输出数据

在输出的第一行需要输出“INTERSECTING LINES OUTPUT”，然后输出每对直线的位置关系，如果是相交则输出“POINT x y”，其中 x 和 y 是交点的两个坐标，保留两位小数。如果两条直线平行则输出“NONE”，表示两直线没有交点。如果两条直线重合则输出“LINE”，表示两条直线的公共点是整个直线。在输出的最后还要输出一行“END OF OUTPUT”。

样例输入

5
0 0 4 4 0 4 4 0
5 0 7 6 1 0 2 3
5 0 7 6 3 -6 4 -3
2 0 2 27 1 5 18 5
0 3 4 0 1 2 2 5

样例输出

INTERSECTING LINES OUTPUT
POINT 2.00 2.00
NONE
LINE
POINT 2.00 5.00
POINT 1.07 2.20
END OF OUTPUT

解题思路

套模板。

源代码

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

#define eps 1e-8
#define inf 1e8

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);
    }
    point operator-(const point &p) const {
        return point(x - p.x, y - p.y);
    }
    point operator*(double k) const {
        return point(x * k, y * k);
    }
    bool operator==(const point &p) const {
        return !sgn(x - p.x) && !sgn(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) { }
    point dir() const { return b - a; }
    double len() const { return dir().mag(); }
};

inline point inter(const line &la, const line &lb) {
    point x(la.b.x - la.a.x, la.b.y - la.a.y);
    point y(lb.a.x - lb.b.x, lb.a.y - lb.b.y);
    point b(lb.a.x - la.a.x, lb.a.y - la.a.y);
    double below = cross(x, y), above1 = cross(b, y);
    double f1 = above1 / below;
    return la.a + (la.b - la.a) * f1;
}

inline bool pol(const point &p, const line &l) {
    return !sgn(cross(l.dir(), p - l.b));
}

inline int rel(const line &la, const line &lb) {

    point u = la.dir(), v = lb.dir();
    double x = u.y * v.x, y = v.y * u.x;

    if (eq(x, y))
        if (pol(la.a, lb))
            return 2;
        else return 0;
    return 1;
}

int main(int argc, char *argv[]) {
    size_t n;
    scanf("%d", &n);
    line a, b; point p;
    printf("INTERSECTING LINES OUTPUT\n");
    while (n--) {
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &a.a.x, &a.a.y, &a.b.x, &a.b.y,
            &b.a.x, &b.a.y, &b.b.x, &b.b.y);
        switch (rel(a, b)) {
        case 0:
            printf("NONE\n");
            break;
        case 1:
            p = inter(a, b);
            if (abs(p.x) < 0.005) p.x = 0.0;
            if (abs(p.y) < 0.005) p.y = 0.0;
            printf("POINT %.2f %.2f\n", p.x, p.y);
            break;
        case 2:
            printf("LINE\n");
            break;
        }
    }
    printf("END OF OUTPUT\n");
    return EXIT_SUCCESS;
}

原创文章，转载请注明来源：http://euyuil.com/2408/poj-1269-intersecting-lines/