这是一道计算几何题，挺锻炼思路的，只是这道题的精度很容易出现问题。开始我也是一直 WA, 搞了一上午。

后来我从网上下了一些说是 AC 了的代码，和我自己的代码比对，用自己写的程序来批量测了很多点，发现如果点的坐标比较大，出现精度问题的概率会小很多。但是如果点的坐标在 -10 ~ 10 之间，就会有相当高的几率出现精度问题。出现的精度问题都是在小数点第二位上，就是四舍五入害死人。经常出现 0.0049999999999 或者 0.0050000000001 之类的东西，如果保留 4 位说不定精度问题就没太大关系了。

感觉就是，两直线相交的算法要写得简单才行，还有就是取一条横线与某条线段交点的算法不能使用通用的两直线相交的算法（反正我这样用了算出的交点就比较不精确），而要自己专门列一个方程来写……

忙了一天之后，我和那个 AC 的程序比较，发现在 -10 ~ 10 之间还有大量数据不一样，都是精度问题，但是想想算了，就直接提交了。没想到 AC 了。

所以可能真的是人品问题，大家慎做此题。

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

POJ 2826 一个简单的问题？！

试想一个平面内，摆放着两条线段，这两条线段的位置关系是未知的，可以是相交也可以是平行之类。然后从这个平面的上方垂直地下起雨来，这两条线段能够“接住”多少面积的雨水呢？

如下图：

左边这图是可以接住雨水的，右边的是一点雨水也接不到啊。

输入数据

输入数据有多组。第一行包含一个数 T 表示有 T 组测试数据。接下来的每组测试数据中，每个数据包含这两条线段的信息，格式参见样例输入。

输出数据

输出每组测试数据中，两条线段能够接到多少雨水。四舍五入保留两位小数。

样例输入

2
0 1 1 0
1 0 2 1
 
0 1 2 1
1 0 1 2

样例输出

1.00
0.00

解题思路

首先判断两线段是否相交，如果不相交那么肯定没戏。然后如果相交的话，求出交点 A. 在交点的上方找出两条线段的端点，如果只能找到一个，说明也没戏；如果能找到两个，就取出其中的较低的那个 P, 作水平线与另一条线段相交，得到一个交点 B. 这个时候再判断 P 的上方会不会被另一条线段“压住”，方法是从 P 作射线看看会不会与另一条线段相交，如果相交又没戏。如果到了这里还有戏，三角形 ABP 的面积就是答案。

重要的是下面这样的情况：

POJ 2826 的三种重要的特殊情况

POJ 2826 的三种重要的特殊情况

源代码

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

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

inline int sgn(double a) {
    return a > eps ? 1 : a < -eps ? -1 : 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) { }
    double &operator[](bool i) { return i ? y : x; }
    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);
    }
    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);
    }
};

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) { }
    line(double x1, double y1, double x2, double y2) :
    a(point(x1, y1)), b(point(x2, y2)) { }
    point &operator[](bool i) { return i ? b : a; }
    point vec() const { return b - a; }
};

inline int relps(const point &p, const line &s) {
    int rp = sgn(cross(p - s.a, s.vec()));
    if (rp) return rp * 3;
    point psa = s.a - p, psb = s.b - p;
    int r = sgn(dot(psa, psb));
    if (r < 0) return 0;
    if (r == 0) return 1;
    return 2;
}

inline int rells(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);
    int sab = sgn(a * b), sa = sgn(a), sb = sgn(b);
    if (sab > 0) return 3;
    if (sab < 0) return 0;
    if (sa || sb) return 1;
    return 2;
}

inline int relssraw(const line &sa, const line &sb) {
    int r; signed char (*p)[4] = (signed char (*)[4])(&r);
    (*p)[0] = relps(sa.a, sb); (*p)[1] = relps(sa.b, sb);
    (*p)[2] = relps(sb.a, sa); (*p)[3] = relps(sb.b, sa);
    return r;
}

inline int relss(const line &sa, const line &sb, int raw) {
    signed char r[4], s[4] = {0};
    *(int *)r = raw;
    if (r[0] * r[1] == -9 && r[2] * r[3] == -9)
        return 0;
    ++s[abs(r[0])]; ++s[abs(r[1])]; ++s[abs(r[2])]; ++s[abs(r[3])];
    if (s[0] == 1 && s[3] == 3) return 1;
    if (s[1] == 2 && s[3] == 2) return 2;
    return 8;
}

inline int relss(const line &sa, const line &sb) {
    return relss(sa, sb, relssraw(sa, sb));
}

inline point inpll(const line &la, const line &lb) {
    double u = cross(la.vec(), point(lb.b - la.b));
    double v = cross(la.vec(), point(lb.a - la.b));
    return (lb.b * v - lb.a * u) / (v - u);
}

int main(int argc, char *argv[]) {

    size_t t; cin >> t;
    while (t--) {
        line u, v; line *ls[2]; ls[0] = &u; ls[1] = &v;
        cin >> u.a.x >> u.a.y >> u.b.x >> u.b.y;
        cin >> v.a.x >> v.a.y >> v.b.x >> v.b.y;
        if (relss(u, v) < 3) {
            point w = inpll(u, v); double area = 0.0;

            for (size_t i = 0; i < 2; ++i) {
                line &tl = *ls[i]; // This line.
                line &al = *ls[!i]; // Another line.
                for (size_t j = 0; j < 2; ++j) {
                    point &tp = tl[j]; // This point.
                    line hor(min(al.a.x, al.b.x)-1.0, tp.y, max(al.a.x, al.b.x)+1.0, tp.y);
                    line ver(tp.x, tp.y, tp.x, max(tp.y, max(al.a.y, al.b.y))+1.0);
                    if (tp.y > w.y && rells(hor, al) < 2 && relss(ver, al) > 7) {
                        point z;
                        z.x = al.a.x + (tp.y-al.a.y) * (al.b.x-al.a.x) / (al.b.y-al.a.y);
                        z.y = tp.y;
                        //point z = inpll(hor, al); // It's not so precise. Why?
                        area = max(area, fabs(cross(w - tp, z - tp)) / 2.0);
                    }
                }
            }

            printf("%0.2lf\n", area);
        } else
            cout << "0.00" << endl;
    }

    return EXIT_SUCCESS;
}

原创文章，转载请注明来源：http://euyuil.com/2547/poj-2826-an-easy-problem/