CC++ & Algorithm

扫描线算法——就像用尺子扫过平面

困难5
语言版本：C++
概述：扫描线算法像一把移动的尺子，一边扫过平面，一边记录遇到的事件，常用于计算矩形面积并或周长。

扫描线算法：从一维到二维，轻松算出重叠面积

你和小伙伴们用长方形卡纸叠在一起拼图，每张卡纸可能互相遮挡。你想知道所有卡纸总共覆盖了多少面积（重叠部分只算一次）。如果一张一张地加，再减去重叠部分，会非常麻烦，尤其当卡纸数量多、形状各不相同时。这时候，扫描线算法就像一把神奇的“尺子”，从左向右慢慢扫过整个平面，每到一条竖边就停下来“量一量”，最后轻松算出总面积。

扫描线算法的核心思想是把二维问题转化成一系列一维问题，通过维护当前y方向被覆盖的总长度，乘以移动的x距离，累加出面积。

一、先热个身：一维扫描线——统计时间段的并集

想象学校有三个社团的活动时间（可能重叠），你想知道总共有多长的时间有活动（重叠部分只算一次）。比如：

  • 足球社：14:00 ~ 16:00
  • 书法社：15:30 ~ 17:30
  • 街舞社：16:00 ~ 18:00

你可以把每个时间段的开始和结束看作事件点，从左到右扫描。用一个计数器 cnt 记录当前有多少个活动在进行中。开始时 cnt = 0。遇到开始事件，cnt 加1；遇到结束事件，cnt 减1。每当 cnt > 0 时，说明这个时间段有活动，累加长度。

时间轴：14:00  15:30  16:00  17:30  18:00
事件：   开始    开始   结束   结束   结束    开始(16:00街舞开始)
                (足球)  (书法) (足球) (书法)  (街舞)

扫描过程：

  • 14:00：cnt=1，从14:00到15:30（下一个事件点）长度=1.5小时，累加。
  • 15:30：cnt=2，从15:30到16:00长度=0.5，累加。
  • 16:00：先处理结束（足球）？注意顺序。如果同一点有多个事件，要小心。通常先处理所有开始，再处理结束，或者统一规则。我们这里简单假设先处理开始，后处理结束。实际上，对于面积并，通常先计算面积再更新，避免同一x重复计算。
  • 16:00：街舞开始 → cnt=3；足球结束 → cnt=2。区间16:00~17:30长度1.5累加。
  • 17:30：书法结束 → cnt=1，区间17:30~18:00长度0.5累加。
  • 18:00：街舞结束 → cnt=0。

总长度 = 1.5+0.5+1.5+0.5=4小时。这个一维的例子就是你理解二维扫描线的钥匙。

二、从一维到二维：矩形面积并

现在回到二维：每个矩形有左右两条竖边（左边界和右边界），我们把这些边按x坐标排序，从左向右移动。移动过程中，用一棵线段树（或简单数组）维护y轴上当前被覆盖的总长度。遇到左边，就在y区间上+1（表示覆盖）；遇到右边，就-1（表示移出）。每次移动到下一个x位置，累加的面积 = 当前覆盖的总长度 × (下一个x - 当前x)。

关键步骤就像做手工：

  1. 拆边：每个矩形拆成左边界（进入）和右边界（离开），记录x坐标，y区间下界y1和上界y2，以及类型（1进入，-1离开）。
  2. 离散化y坐标：因为y可能很大（比如0到10^9），不能直接开数组。我们把所有出现的y坐标收集起来排序、去重，然后把每个矩形的y1、y2映射到离散化后的索引。
  3. 排序边：所有竖边按x坐标从小到大排序。
  4. 扫描：维护覆盖次数数组cover（大小为离散化后的y区间数-1），记录每一个小区间被覆盖的次数。从左到右遍历边，先根据当前cover计算y方向总覆盖长度（覆盖次数>0的区间长度和），再乘以本次移动的x距离，累加到面积中；然后更新区间覆盖（将当前竖边对应的y区间加上type）。
  5. 注意边界：通常用左闭右开区间，比如矩形y从y1到y2，我们只覆盖[y1, y2-1]这些整数段（如果坐标是离散点，则覆盖区间的索引）。离散化后，相邻y坐标之间的长度就是y[i+1] - y[i]。

三、新手容易掉进的坑

1. 忘记离散化或离散化出错

如果不离散化，直接拿y坐标当数组下标，会超界或浪费内存。离散化时要小心：映射关系要一一对应，且覆盖区间要用左闭右开。

2. 区间覆盖的边界处理

比如矩形 y1=1, y2=3。如果用数组cover表示从y到y+1的区间，那么需要更新索引1和2（即y1到y2-1）。如果写成for(y=y1; y<=y2; y++)会多算一个单位，导致面积偏大。

3. 扫描时x相同的情况

如果多个竖边在同一x坐标（比如两个矩形共边），顺序很重要。通常先计算面积，再更新覆盖，否则会在移动距离为0时错误累加。或者处理完所有同一x的边后统一更新。标准做法：遍历边时，当x改变时才计算面积；对于相同x的边，先更新覆盖，然后下一次遇到新x时计算面积。这样可以避免重复计算。

4. 数据类型溢出

坐标范围可能很大（10^9），矩形数量多（10^5），面积可能超过int范围，记得用long long。

四、完整可运行代码示例（含离散化）

下面给出一个完整的C++代码，假设矩形坐标是整数，使用离散化+数组维护覆盖长度（适用于矩形数量较少时，比如y离散化后不超过1000）。代码中每行变量都加了中文注释，方便理解。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定义竖边结构体
struct Line {
    int x;      // 竖边的x坐标
    int y1, y2; // 竖边的y下界和上界（原始坐标）
    int type;   // 左边界为1（进入），右边界为-1（离开）
};

// 按x坐标从小到大排序
bool cmp_by_x(Line a, Line b) {
    return a.x < b.x;
}

int main() {
    // 三个矩形： (x1,y1)左下角 (x2,y2)右上角
    vector<vector<int>> rects = {
        {1, 1, 4, 4},
        {2, 2, 6, 5},
        {3, 0, 5, 3}
    };

    // 1. 收集所有y坐标，用于离散化
    vector<int> y_vals;
    for (auto r : rects) {
        y_vals.push_back(r[1]); // y1
        y_vals.push_back(r[3]); // y2
    }
    // 排序并去重
    sort(y_vals.begin(), y_vals.end());
    y_vals.erase(unique(y_vals.begin(), y_vals.end()), y_vals.end());

    // 2. 将每个矩形拆成左右两条竖边，同时把y坐标映射到离散化后的索引
    vector<Line> lines;
    for (auto r : rects) {
        int y1_idx = lower_bound(y_vals.begin(), y_vals.end(), r[1]) - y_vals.begin(); // 下界索引
        int y2_idx = lower_bound(y_vals.begin(), y_vals.end(), r[3]) - y_vals.begin(); // 上界索引
        // 左边界
        lines.push_back({r[0], y1_idx, y2_idx, 1});
        // 右边界
        lines.push_back({r[2], y1_idx, y2_idx, -1});
    }

    // 3. 按x坐标排序所有竖边
    sort(lines.begin(), lines.end(), cmp_by_x);

    // 4. 准备覆盖数组：覆盖次数记录在每个离散化区间上（区间数 = y_vals.size()-1）
    int n_y = y_vals.size();          // y坐标个数
    vector<int> cover(n_y - 1, 0);    // cover[i] 表示第i个小区间（y_vals[i]~y_vals[i+1]）被覆盖的次数

    long long total_area = 0;         // 总面积，用long long防止溢出
    int prev_x = lines[0].x;          // 上一个处理的x坐标

    // 5. 开始扫描
    for (Line &line : lines) {
        // 先计算从prev_x到当前x之间矩形的面积
        int x_len = line.x - prev_x;
        if (x_len > 0) {
            // 计算当前y方向被覆盖的总长度
            int covered_len = 0;
            for (int i = 0; i < n_y - 1; i++) {
                if (cover[i] > 0) {
                    // 区间长度 = y_vals[i+1] - y_vals[i]
                    covered_len += y_vals[i+1] - y_vals[i];
                }
            }
            total_area += (long long)covered_len * x_len; // 累加面积
        }

        // 更新覆盖：在区间 [y1_idx, y2_idx-1] 上加type
        for (int i = line.y1; i < line.y2; i++) { // 注意是左闭右开
            cover[i] += line.type;
        }

        prev_x = line.x; // 更新上一个x
    }

    // 输出结果
    cout << "总面积并 = " << total_area << endl; // 预期输出13
    return 0;
}

这段代码可以直接拷贝运行，结果应该是13，你可以自己验证。

五、拓展：当矩形数量很多时——线段树登场

上面用数组维护覆盖长度，每次更新和查询都要遍历所有y区间，时间复杂度是O(N × M)，其中M是离散化后的区间数，矩形数量N增加时效率很低。竞赛中常用线段树来维护覆盖次数和覆盖长度，支持区间加（+1/-1）和区间查询（当前覆盖长度），复杂度可以降到O(N log N)。

线段树每个节点存储两个信息：

  • cnt：该区间被完整覆盖的次数（不向下传递）。
  • len：该区间中覆盖长度大于0的总长度。

当 cnt > 0 时，len = 整个区间长度；否则，len = 左右子节点的 len 之和。

这样，每次更新一个区间（加1或减1）后，根节点的 len 就是当前y方向被覆盖的总长度。扫描时只需查询根节点的 len 即可，无需遍历。

学习线段树是掌握高效扫描线算法的关键。

六、相关知识点指引

  • 离散化：把连续的坐标映射成小范围的整数，减少空间消耗。在扫描线中几乎必须使用。
  • 线段树：用于动态维护区间覆盖问题，是扫描线加速的利器。
  • 事件驱动思想：扫描线算法本质是事件驱动（遇到进入事件操作，遇到离开事件操作），这种思想在解题中非常常见，比如区间调度、窗口滑动等。

从卡纸拼图到复杂几何计算，扫描线算法让我们可以用“一把尺子”优雅地解决问题。掌握了它，二维图形面积、周长等难题都会变得简单起来。

例题精讲

1单选题

在扫描线算法中，对于事件点（矩形的左右边）的排序规则通常是什么？

A按x坐标升序，若x相同则左边界优先于右边界
B按x坐标升序，若x相同则右边界优先于左边界
C按y坐标升序，若y相同则下边界优先于上边界
D按矩形面积大小升序
2判断题

扫描线算法只能用于计算矩形的面积并，不能用于计算矩形的周长并。

3填空题
以下是使用扫描线算法求矩形面积并的C++代码片段（使用线段树维护当前覆盖长度）。请补全"更新当前覆盖长度"的线段树操作函数。

struct SegTree {
    int cnt; // 被完全覆盖的次数
    double len; // 当前区间被覆盖的长度
} tree[N * 8];

void pushup(int p, int l, int r) {
    if (tree[p].cnt > 0) {
        tree[p].len = ___(1)___;
    } else {
        tree[p].len = ___(2)___;
    }
}
4单选题

在扫描线算法中，通常使用什么数据结构来高效维护当前扫描线在y方向上的覆盖长度？

A二叉堆
B并查集
C线段树（支持区间更新和查询）
D树状数组
5判断题

扫描线算法处理矩形面积并问题时，时间复杂度为O(n log n)，其中n为矩形数量。