跳转至

扫描线

矩形面积并

P5490 【模板】扫描线 & 矩形面积并

求 \(n\) 个四边平行于坐标轴的矩形的面积并。

对于 \(100\%\) 的数据，\(1 \le n \le {10}^5\)， \(0 \le x_1 < x_2 \le {10}^9\)， \(0 \le y_1 < y_2 \le {10}^9\)。

实现 
 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
#include <bits/stdc++.h>
#define lson (x << 1)
#define rson (x << 1 | 1)
using namespace std;
const int MAXN = 1e6 + 10;
typedef long long ll;
int n, cnt = 0;
ll x1, y1, x2, y2, X[MAXN << 1];
struct ScanLine
{
    ll l, r, h;
    int mark;
    bool operator<(const ScanLine &rhs) const { return h < rhs.h; }
} line[MAXN << 1];
struct SegTree
{
    int l, r, sum;
    ll len;
} tree[MAXN << 2];
void build(int x, int l, int r)
{
    tree[x].l = l, tree[x].r = r;
    tree[x].len = 0;
    tree[x].sum = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    return;
}
void pu(int x)
{
    int l = tree[x].l, r = tree[x].r;
    if (tree[x].sum)
        tree[x].len = X[r + 1] - X[l];
    else
        tree[x].len = tree[lson].len + tree[rson].len;
}
void update(int x, ll L, ll R, int c)
{
    int l = tree[x].l, r = tree[x].r;
    if (X[r + 1] <= L || R <= X[l]) return;
    if (L <= X[l] && X[r + 1] <= R)
    {
        tree[x].sum += c;
        pu(x);
        return;
    }
    update(lson, L, R, c);
    update(rson, L, R, c);
    pu(x);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lli %lli %lli %lli", &x1, &y1, &x2, &y2);
        X[2 * i - 1] = x1, X[2 * i] = x2;
        line[2 * i - 1] = (ScanLine){x1, x2, y1, 1};
        line[2 * i] = (ScanLine){x1, x2, y2, -1};
    }
    n <<= 1;
    sort(line + 1, line + n + 1);
    sort(X + 1, X + n + 1);
    int tot = unique(X + 1, X + n + 1) - X - 1;
    build(1, 1, tot - 1);
    ll ans = 0;
    for (int i = 1; i < n; i++)
    {
        update(1, line[i].l, line[i].r, line[i].mark);
        ans += tree[1].len * (line[i + 1].h - line[i].h);
    }
    printf("%lli", ans);
    return 0;
}