形式化题目

给定平面上的 $n$ 个轴平行闭矩形 $R_k = [x_{1k}, x_{2k}] \times [y_{1k}, y_{2k}]$， 其中 $x_{1k} < x_{2k}$、$y_{1k} < y_{2k}$，坐标可为实数。要求所有矩形的面积并

即被至少一个矩形覆盖的区域的面积，重复覆盖只计算一次。坐标可以不是整数，需要按浮点处理。 坐标系方向（题面 $x$ 向下、$y$ 向右）只影响方位命名，不影响面积，下面按普通坐标轴说明。

数据范围：$1 \leqslant n \leqslant 10000$，$0 \leqslant x_1 < x_2 \leqslant 100000$， $0 \leqslant y_1 < y_2 \leqslant 100000$；$n = 0$ 表示输入结束。

样例：两个矩形 $(10,10,20,20)$ 与 $(15,15,25,25.5)$，重叠区是 $[15,20]\times[15,20]$，面积 $100 + 105 - 25 = 180$，故答案为 180.00。

暴力解法

思路

面积并的原始定义是「被覆盖点集的测度」，最直接的切入点是把平面切碎成小块， 逐块判断是否被覆盖。切分的关键依据是：

任何矩形的 $x$ 边界只会出现在 $x_{1k}$ 或 $x_{2k}$ 处， 所以把全部 $x$ 坐标排序去重得到 $x_1^* < x_2^* < \cdots < x_X^*$ 后， 每个竖条 $[x_i^*, x_{i+1}^*)$ 内部不包含任何矩形的竖直边。

由此得到一个竖条内的覆盖情况是恒定的：矩形 $R_k$ 要么完整盖住整个竖条的 $x$ 跨度， 要么与它完全不相交，不存在「盖一半」的矩形。于是

括号内是一个一维问题：把 $S_i$ 中矩形的 $y$ 区间排序后从左往右合并， 累加各段长度即可。

样例的两个矩形产生 $x$ 坐标 $\{10, 15, 20, 25\}$，对应 3 个竖条（$R_1 = [10,20]\times[10,20]$， $R_2 = [15,25]\times[15,25.5]$）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14 25.5 |                 +-------------------------+   <- R2 上边
      |                 | R2                      |
      |                 |                         |
   20 |    +------------+------------+            |   <- R1 上边 (与 R2 相交)
      |    | R1         |            |            |
      |    |            |            |            |
   15 |    |            +------------+------------+   <- R2 下边 (与 R1 相交)
      |    |                         |
      |    |                         |
   10 |    +-------------------------+               <- R1 下边
      +----+------------+------------+------------+
          10           15           20           25
          |            |            |            |
          └─ 竖条1 ─────┴─ 竖条2 ────┴─ 竖条3 ────┘

三个竖条贡献相加 $50 + 77.5 + 52.5 = 180$，与样例一致。 观察点：竖条 2 里两个矩形都参与，一维合并把重叠的 $[15,20]$ 只算了一次—— 这就是「重复覆盖只计一次」在实现层面的落点。

代码

复杂度

• 时间 $O(n^2 \log n)$：竖条数 $X - 1 = O(n)$；每个竖条要 $O(n)$ 筛选矩形， 再对至多 $n$ 个区间排序合并 $O(n \log n)$。$n = 10^4$ 时约 $10^8$ 量级，Python 必然超时。
• 空间 $O(n)$。

瓶颈

瓶颈不在「离散化」这一步——竖条的划分是必要的，问题出在每个竖条都要从头重算：

1. 筛选 $S_i$ 需要扫一遍全部 $n$ 个矩形；
2. 求出 $S_i$ 后还要重新排序、重新合并一遍 $y$ 区间。

但相邻竖条的 $S_i$ 之间只差「在 $x_{i+1}^*$ 结束的矩形」与「在 $x_{i+1}^*$ 开始的矩形」， 覆盖长度的变化是增量的。既然只有竖边处会变，为每个竖条重做一次完整的一维区间并 就是纯粹的浪费。

正解

关键观察

把「关注竖条」换成「关注竖边」，瓶颈立刻消失：

矩形 $R_k$ 的两条竖直边 $x = x_{1k}$、$x = x_{2k}$ 携带增量 $+1$、$-1$。 按 $x$ 升序依次处理（同 $x$ 的边连续处理），则处理完 $x_{\text{prev}}$ 处的全部竖边后， $y$ 轴上被覆盖的总长度，就是区间 $[x_{\text{prev}}, x_{\text{next}})$ 上的覆盖长度。

展开就是：进入竖条 $[x_i^*, x_{i+1}^*)$ 的矩形满足 $x_{1k} \leqslant x_i^*$ 且 $x_{2k} \geqslant x_{i+1}^*$。 对竖条内任意 $y$，$R_k$ 覆盖它的充要条件是 $x_{1k} \leqslant x_i^*$ 且 $x_{2k} > x_i^*$ （因为 $x_i^*$ 与 $x_{i+1}^*$ 之间没有矩形的竖直边，$x_{2k} > x_i^*$ 会自动加强为 $x_{2k} \geqslant x_{i+1}^*$）。 而「$+1$ 边已处理」等价于 $x_{1k} \leqslant x_i^*$，「$-1$ 边未处理」等价于 $x_{2k} > x_i^*$， 二者的次数差就是该 $y$ 处被覆盖的次数。于是这个集合在整段上不变， 「当前总覆盖长度」是一个只依赖已处理竖边的量，可以增量维护， 不必每个竖条重新求区间并。

剩下的问题变成：维护一个 $y$ 轴上的动态区间加 / 询问总覆盖长度结构。 这正是线段树的经典应用——把所有 $y_{1k}, y_{2k}$ 离散化， 在「段」上做区间加 $\pm 1$，并维护整棵树被覆盖的长度。

思路

第一步，离散化 $y$。 把全部 $y_{1k}, y_{2k}$ 排序去重得到 $m + 1$ 个坐标， 形成 $m$ 个基本段，第 $i$ 段是 $[y_i, y_{i+1}]$，长度 $y_{i+1} - y_i$。 线段树就建在这 $m$ 个段上（叶子是段，不是点）。矩形 $R_k$ 落在段编号 $[\text{rank}(y_{1k}),\ \text{rank}(y_{2k}) - 1]$ 上，因为 $y_{2k}$ 是段的右端点， 不应该再往右多算一段。

第二步，确定每个结点存什么。 每个结点维护两个值：

• cover_cnt：完整覆盖该结点段区间的竖边条数。关键性质是它不下传；
• cover_len：该结点段区间内被覆盖的总长度。

回填（pushup）规则：

为什么 cover_cnt 不下传也正确？因为一个结点只有两种状态： 被整段覆盖时长度由自己决定（哪怕子结点什么都没记）， 否则长度必然等于左右儿子之和。被部分覆盖的信息已经记在更深层的结点上， 父结点不需要重复计数，也不会漏算。

第三步，扫描竖边。 把 $2n$ 条竖边 $(x, l, r, \pm 1)$ 按 $x$ 升序排序 （$l, r$ 是段编号，$r$ 含端点；为与代码对应，记 $m = \text{seg\_cnt}$）， 顺序处理：先按「上一条边之后的状态」结算区间 $[x_{\text{prev}}, x)$， 再应用本条边的区间加。结算必须在更新之前，这是最容易写反的地方。

1
2
3
4
5area = 0; prev_x = edges[0].x
for (x, l, r, d) in edges:
    area += cover_len[根] * (x - prev_x)    # 结算 [prev_x, x)，此时树里只有 x' <= prev_x 的边
    cover(1, 0, m-1, l, r, d)               # 再应用本条边
    prev_x = x

样例的 4 条竖边（$y$ 去重后为 $10, 15, 20, 25.5$，$m = 3$ 段：$[10,15],[15,20],[20,25.5]$， 编号 $0,1,2$）：

四段贡献 $0 + 50 + 77.5 + 52.5 = 180$，与暴力层竖条表逐条对应： 第 $j$ 行的「结算前 cover_len」正是第 $j$ 个竖条的覆盖长度。 观察点有两个：一是第一行 $\Delta x = 0$（还没走过任何宽度）， 二是相同 $x$ 上的多条竖边可以任意顺序处理，因为此时 $\Delta x = 0$， 中间不会插入错误的贡献。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 亚特兰蒂斯：矩形面积并，按 x 扫描竖边，线段树维护被覆盖的 y 总长度。
#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

struct Rect {
    double x1, y1, x2, y2;
};

struct Edge {
    double x;
    ll ql, qr;   // 基本段区间 [ql, qr]
    ll delta;    // 左边界 +1、右边界 -1
};

std::vector<double> ys;      // 离散化后的 y 坐标
std::vector<ll> cover_cnt;   // 结点被整段覆盖的次数
std::vector<double> cover_len; // 结点内被覆盖的总长度

bool edge_less(const Edge& a, const Edge& b) {
    if (a.x != b.x) return a.x < b.x;
    if (a.ql != b.ql) return a.ql < b.ql;
    if (a.qr != b.qr) return a.qr < b.qr;
    return a.delta < b.delta;
}

// 把基本段区间 [ql, qr] 的覆盖次数加 delta，再回填本结点的覆盖长度
void cover(ll node, ll nl, ll nr, ll ql, ll qr, ll delta) {
    if (ql <= nl && nr <= qr) { // 整段落在同一条竖边的跨度里
        cover_cnt[node] += delta;
    } else {
        ll mid = (nl + nr) >> 1;
        if (ql <= mid) cover(node << 1, nl, mid, ql, qr, delta);
        if (qr > mid) cover(node << 1 | 1, mid + 1, nr, ql, qr, delta);
    }
    if (cover_cnt[node]) { // 被完整覆盖：整段都算
        cover_len[node] = ys[nr + 1] - ys[nl];
    } else if (nl == nr) {
        cover_len[node] = 0.0;
    } else {
        cover_len[node] = cover_len[node << 1] + cover_len[node << 1 | 1];
    }
}

double union_area(std::vector<Rect>& rects) {
    ys.clear();
    for (size_t i = 0; i < rects.size(); i++) {
        ys.push_back(rects[i].y1);
        ys.push_back(rects[i].y2);
    }
    std::sort(ys.begin(), ys.end());
    ys.erase(std::unique(ys.begin(), ys.end()), ys.end());

    ll seg_cnt = (ll)ys.size() - 1; // 基本段个数：第 i 段是 [ys[i], ys[i+1]]
    cover_cnt.assign(4 * seg_cnt + 4, 0);
    cover_len.assign(4 * seg_cnt + 4, 0.0);

    std::vector<Edge> edges;
    for (size_t i = 0; i < rects.size(); i++) {
        ll r1 = std::lower_bound(ys.begin(), ys.end(), rects[i].y1) - ys.begin();
        ll r2 = std::lower_bound(ys.begin(), ys.end(), rects[i].y2) - ys.begin();
        Edge e;
        e.x = rects[i].x1; e.ql = r1; e.qr = r2 - 1; e.delta = 1;  edges.push_back(e);
        e.x = rects[i].x2; e.ql = r1; e.qr = r2 - 1; e.delta = -1; edges.push_back(e);
    }
    std::sort(edges.begin(), edges.end(), edge_less);

    double area = 0.0;
    double prev_x = edges[0].x;
    for (size_t i = 0; i < edges.size(); i++) {
        area += cover_len[1] * (edges[i].x - prev_x); // 区间 [prev_x, x) 用移动前的覆盖长度
        cover(1, 0, seg_cnt - 1, edges[i].ql, edges[i].qr, edges[i].delta);
        prev_x = edges[i].x;
    }
    return area;
}

int main() {
    ll n;
    ll case_id = 0;
    while (scanf("%lld", &n) == 1 && n != 0) {
        case_id++;
        std::vector<Rect> rects(n);
        for (ll i = 0; i < n; i++) {
            scanf("%lf %lf %lf %lf", &rects[i].x1, &rects[i].y1, &rects[i].x2, &rects[i].y2);
        }
        double area = union_area(rects);
        printf("Test case #%lld\nTotal explored area: %.2f\n\n", case_id, area);
    }
    return 0;
}

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 17:54
# update_at: 2026-10-01 17:54

import sys


def union_area(rects: list[tuple[float, float, float, float]]) -> float:
    """所有矩形的面积并：按 x 扫竖边，线段树维护当前竖线上被覆盖的 y 总长度。"""
    ys = sorted({y for _x1, y1, _x2, y2 in rects for y in (y1, y2)})  # 离散化后的 y 坐标
    y_rank = {y: i for i, y in enumerate(ys)}                          # y 坐标 → 下标
    seg_cnt = len(ys) - 1                        # 基本段个数：第 i 段是 [ys[i], ys[i+1]]
    cover_cnt = [0] * (4 * seg_cnt)              # 结点被整段覆盖的次数
    cover_len = [0.0] * (4 * seg_cnt)            # 结点内被覆盖的总长度

    def cover(node: int, nl: int, nr: int, ql: int, qr: int, delta: int) -> None:
        """把基本段区间 [ql, qr] 的覆盖次数加 delta，再回填本结点的覆盖长度。"""
        if ql <= nl and nr <= qr:                # 整段落在同一条竖边的跨度里
            cover_cnt[node] += delta
        else:
            mid = (nl + nr) >> 1
            if ql <= mid:
                cover(node << 1, nl, mid, ql, qr, delta)
            if qr > mid:
                cover(node << 1 | 1, mid + 1, nr, ql, qr, delta)
        if cover_cnt[node]:                      # 被完整覆盖：整段都算
            cover_len[node] = ys[nr + 1] - ys[nl]
        elif nl == nr:                           # 叶子没被覆盖，长度为 0
            cover_len[node] = 0.0
        else:                                    # 否则由两个子结点拼接
            cover_len[node] = cover_len[node << 1] + cover_len[node << 1 | 1]

    edges = sorted(                              # 竖边：左边界 +1、右边界 -1
        (x, y_rank[y1], y_rank[y2] - 1, delta)
        for x1, y1, x2, y2 in rects
        for x, delta in ((x1, 1), (x2, -1))
    )
    area = 0.0
    prev_x = edges[0][0]
    for x, ql, qr, delta in edges:
        area += cover_len[1] * (x - prev_x)      # 区间 [prev_x, x) 用移动前的覆盖长度
        cover(1, 0, seg_cnt - 1, ql, qr, delta)
        prev_x = x
    return area


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    case = 0

    while (n := int(next(data))) != 0:
        case += 1
        rects = [
            (float(next(data)), float(next(data)), float(next(data)), float(next(data)))
            for _ in range(n)
        ]
        out += [f"Test case #{case}", "Total explored area: %.2f" % union_area(rects), ""]

    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    solve()

实现说明：

• union_area 的前三行是离散化：ys 排序去重、y_rank 做坐标到下标的映射、 seg_cnt = len(ys) - 1 是基本段数。
• cover 是内嵌的线段树区间加：ql <= nl and nr <= qr 时才改动 cover_cnt[node]， 否则递归到左右儿子，最后统一 pushup。递归深度 $O(\log n)$，不会爆栈。
• cover_len / cover_cnt 用长度 $4 \cdot \text{seg\_cnt}$ 的扁平列表存放， 下标 1 为根，node << 1、node << 1 | 1 为左右儿子； Python 里没有 pushdown，正好对应「cover_cnt 不下传」的设计。
• edges 生成式把每个矩形同时产出两条竖边， 右端点写成 y_rank[y2] - 1，见上文「第一步」的解释。
• solve 按空白切分整份输入并用指针 pos 顺序读， n = 0 时 while 立即结束，恰好对应题面「该用例无需处理」。

复杂度

• 时间 $O(n \log n)$：竖边排序 $O(n \log n)$；$2n$ 条竖边各做一次 $O(\log n)$ 的区间加，每次 pushup 是常数次算术；面积累加 $O(n)$。 离散化排序同样 $O(n \log n)$。
• 空间 $O(n)$：ys、y_rank、edges 与两棵四倍数组均为线性。

总结

• 破题点是竖条内部覆盖状态恒定：所有矩形的竖直边只落在有限个 $x$ 坐标上， 于是二维面积并可拆成有限个竖条，竖条内的覆盖是一维区间并。
• 暴力做法每个竖条重算一次区间并，瓶颈是 $O(n^2\log n)$； 观察到相邻竖条之间只差一小部分竖边，把「竖条」换成「竖边事件」， 覆盖长度就能增量维护。
• 增量维护的工具是线段树：cover_cnt 记录整段被覆盖次数且不下传， cover_len 按「整段覆盖→段长 / 叶子→0 / 否则左右相加」回填， 区间加与询问都是 $O(\log n)$。
• 扫描线上两个容易写错的细节：先结算 $\Delta x$ 再更新； 以及 y 区间是段不是点，右端点要减 1。
• 同一套模型可以直接推广到矩形周长并：把面积换成「相邻竖条覆盖长度之差」 与「竖条内被覆盖段数」，只需要在线段树上多维护一个段数与左右端点是否被覆盖。