跳转至

半平面交

求多个凸多边形的交的面积

例题

P4196 [CQOI2006] 凸多边形 /【模板】半平面交 - 洛谷

求 \(n\) 个凸多边形的面积交

代码
C++
 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
{ 计算几何基础 }
vector<Point> points[10];
vector<Line> lines;
int deq[505];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0 ; i < n ; i++) {
        int m;
        cin >> m;
        points[i].resize(m);
        for (int j = 0 ; j < m ; j++) {
            cin >> points[i][j];
        }
        for (int j = 0 ; j < m ; j++) {
            lines.emplace_back(points[i][j], points[i][(j + 1) % m]);
        }
    }
    sort(begin(lines), end(lines));
    lines.resize(unique(begin(lines), end(lines)) - begin(lines));
    auto check = [&](int i, int j, int k) {
        Point x = getLineIntersection(lines[j], lines[k]);
        return sgn(cross(x, lines[i].p1, lines[i].p2)) < 0;
    };
    int L = 1, R = 0;
    deq[++R] = 0;
    deq[++R] = 1;
    int len = lines.size();
    for (int i = 2 ; i < len ; i++) {
        while (L < R && check(i, deq[R], deq[R - 1])) {
            R--;
        }
        while (L < R && check(i, deq[L], deq[L + 1])) {
            L++;
        }
        deq[++R] = i;
    }
    while (L < R && check(deq[L], deq[R - 1], deq[R])) {
        R--;
    }
    while (L < R && check(deq[R], deq[L], deq[L + 1])) {
        L++;
    }
    vector<Point> res;
    for (int i = L ; i < R ; i++) {
        res.emplace_back(getLineIntersection(lines[deq[i]], lines[deq[i + 1]]));
    }
    if (R - L > 1) {
        res.emplace_back(getLineIntersection(lines[deq[R]], lines[deq[L]]));
    }
    len = res.size();
    Tdouble ans = 0;
    for (int i = 0 ; i < len ; i++) {
        ans += cross(res[i], res[(i + 1) % len]);
    }
    cout << fixed << setprecision(3) << fabs(ans) / 2 << "\n";
    return 0;
}