OI-wiki 计算几何扫描线算法全解：矩形面积并、二维数点与 B 维正交范围

OI-wiki 计算几何扫描线算法全解：矩形面积并、二维数点与 B 维正交范围

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

扫描线（Sweep Line）是计算几何与数据结构交叉领域中最常用的经典技术之一：它用一条虚拟直线"扫过"整个平面，把静态的二维问题转化为动态的一维问题，再由线段树或树状数组等数据结构在线维护。本文以 OI-wiki 的 scanning.md 为主体，结合仓库内docs/geometry/code/scanning/下的 5 份完整可运行参考代码，系统讲解扫描线在矩形面积并、B 维正交范围与二维数点三大场景下的推导过程、实现细节与复杂度分析，帮助你从"看得懂思路"进阶到"闭卷写出正确代码"。

引入：什么是扫描线

扫描线算法在图形上的运用与它的字面意思十分相似：一条线在整个图上扫来扫去。这条线每扫过一个关键位置，就会触发一次对"当前状态"的修改与统计。它通常被用来解决三类问题：

• 图形的面积（如多个矩形的并集面积）；
• 图形的周长（如矩形并的轮廓周长）；
• 二维数点（二维正交范围内的点数统计）。

扫描线之所以高效，核心在于"化静为动"：二维问题的修改与查询发生在同一平面内，直接处理往往需要平方级复杂度；而用扫描线枚举其中一个维度后，另一维度上的操作被压缩成序列上的区间修改与区间/前缀查询，复杂度降为 $O((n+m)\log n)$ 级别。

二维矩形面积并问题

问题描述：在二维坐标系中给定多个矩形（每个矩形由左下角与右上角坐标给出），求所有矩形覆盖区域的并集面积。

当矩形数量很小时，可以暴力枚举每一条竖线切开图形逐块累加；但当数据规模变大（例如 $n \le 10^5$），就必须借助扫描线。

算法过程

1. 切分：用一条从下往上移动的水平线扫描整个图形。每扫过一条水平边，图形就被横向切开一次，最终整个矩形并集被切成一系列颜色各异的小矩形。每个小矩形的高就是两次扫描之间的竖直距离，而它的水平宽度则在不断变化。

2. 标记上下边：给每个矩形的下边标记为 $1$，上边标记为 $-1$。每当扫描线遇到一条水平边，就在这条边（于横轴上的投影区间）上加上对应标记。这个操作与遍历括号序列完全同构——开括号加 $1$、闭括号减 $1$，当前区间的"权值"对应当前扫描位置的深度，而"权值是否大于 $0$"对应当前位置是否位于某个矩形内部，即这段区间是否计入小矩形的宽度。

3. 累加面积：在任意两次相邻水平边之间，小矩形（可能不止一个）的总宽度就是整个数轴上权值大于 $0$ 的区间总长度；将其乘以两条水平边的纵坐标之差，便得到这一薄片的面积。对所有薄片求和即为总面积。

面积和 = Σ (当前水平边高度 - 上一条水平边高度) × 当前"覆盖长度"

线段树维护：为什么朴素模板不行

扫描线需要用数据结构维护矩形的"长"，即整个数轴上覆盖次数大于 $0$ 的区间总长度。需求的本质是两条：

• 一段区间权值加 $1$ / 减 $1$（区间加）；
• 统计整个数轴上，区间权值大于 $0$ 的区间长度和（全局查询）。

如果你尝试直接用普通线段树模板（维护区间和的懒标记写法）来实现，会遇到一些挫折：区间加时即使修改区间与节点管理区间完全重合，依然无法在常数时间推出覆盖次数如何变化——因为我们无法直接知道：这个管理范围里有多长的区间会从 $1$ 变成 $0$（或从 $0$ 变成 $1$）。覆盖次数在 $1$ 与 $0$ 之间跳变的位置取决于子区间的覆盖状态，无法用单一的"区间和"信息刻画。

解法：这道题只需朴素的分治，即维护每个节点两个信息（见 scanning_1.cpp 中的v[]与w[]）：

• v[]：该节点管理区间被完全覆盖的次数（类似不下传的懒标记，记录该区间整体被多少个矩形横跨）；
• w[]：该节点管理区间内已覆盖（覆盖次数 > 0）的总长度。

pushup的合并逻辑是：若v[u] > 0，说明整个区间被完全覆盖，w[u]直接等于区间原始长度；否则w[u]等于左右儿子w之和（叶子节点则为 $0$）。由于我们从不把v下传到儿子，线段树需要开4 倍以上空间（参考代码开 8 倍以兼容对叶子节点w[2u+1]的访问）。

注意：扫描线的修改与查询都发生在离散化后的坐标下标上，因此需要先对横坐标做 离散化。

参考实现一：洛谷 P5490 模板题（整数坐标）

以下代码来自 scanning_1.cpp，思路为水平扫描 + 线段树维护覆盖长度，读者可在 洛谷 P5490 上直接验证：

#include <algorithm> #include <iostream> using ll = long long; constexpr int N = 1e5 + 1; int n, a[N * 2], tot; // a[] 和 tot 用于把 x 离散化 ll v[N * 8], w[N * 8]; // 完全覆盖区间的次数、已覆盖的长度 struct St { ll x1, x2, y, o; } b[N * 2]; // 矩形上下边缘 int f(int y) { // 离散化，把坐标映射到 a 中的下标 return std::lower_bound(a, a + tot, y) - a; } void up(int u, int ul, int ur) { // pushup if (v[u]) w[u] = a[ur] - a[ul]; // 如果对叶子节点调用 w[u*2+1]，那么线段树需要开 8 倍空间 // 乘上矩形上下两边就是 16 倍 else if (ul + 1 == ur) w[u] = 0; else w[u] = w[u * 2 + 1] + w[u * 2 + 2]; } void add(int lf, int rg, ll o, int u = 0, int ul = 0, int ur = tot - 1) { // 区间加 if (lf == ul && rg == ur) return v[u] += o, up(u, ul, ur), void(); int um = (ul + ur) / 2; if (lf < um) add(lf, std::min(rg, um), o, u * 2 + 1, ul, um); if (um < rg) add(std::max(lf, um), rg, o, u * 2 + 2, um, ur); up(u, ul, ur); } int main() { std::cin >> n; for (int i = 0, x1, x2, y1, y2; i < n; i++) { // y1 是局部变量不会重名 std::cin >> x1 >> y1 >> x2 >> y2; b[i] = {x1, x2, y1, 1}; b[i + n] = {x1, x2, y2, -1}; a[i] = x1, a[i + n] = x2; } std::sort(a, a + n * 2), tot = 1; for (int i = 1; i < n * 2; i++) if (a[i] != a[tot - 1]) a[tot++] = a[i]; // 离散化 std::sort(b, b + n * 2, [](St &i, St &j) -> bool { return i.y < j.y; }); // 操作排序 ll sum = 0; add(f(b[0].x1), f(b[0].x2), 1); for (int i = 1; i < n * 2; i++) { int x1 = f(b[i].x1), x2 = f(b[i].x2); sum += (b[i].y - b[i - 1].y) * w[0]; // 对每个小矩形面积求和 add(x1, x2, b[i].o); } std::cout << sum << '\n'; }

代码要点：

• 每个矩形拆成两条水平边{x1, x2, y, o}，下边o = 1、上边o = -1；
• a[]收集所有x1/x2后排序去重完成离散化，f()用lower_bound把真实坐标映射为下标；
• 先加入第一条边再进入循环，每次用w[0]（根节点的覆盖总长）乘以上下两条水平边的高度差累加面积；
• 线段树区间采用左闭右开的[ul, ur)写法，注意与常见写法下标差异。

仓库同时提供了本题的测试数据：输入样例 scanning_1.in 给出两个矩形(100,100)-(200,200)与(150,150)-(250,255)，期望输出 scanning_1.ans 为18000，可用于快速自测。

参考实现二：POJ 1151 Atlantis（浮点坐标）

当矩形顶点坐标是浮点数时，离散化与线段树维护的对象变为实数区间。参考代码 scanning_2.cpp 采用了从右向左扫描竖边的对称写法（与 P5490 的水平扫描互为镜像）：

#include <algorithm> #include <cstdio> #include <cstring> constexpr int MAXN = 300; using namespace std; int lazy[MAXN << 3]; // 标记了这条线段出现的次数 double s[MAXN << 3]; struct node1 { double l, r; double sum; } cl[MAXN << 3]; // 线段树 struct node2 { double x, y1, y2; int flag; } p[MAXN << 3]; // 坐标 // 定义sort比较 bool cmp(node2 a, node2 b) { return a.x < b.x; } // 上传 void pushup(int rt) { if (lazy[rt] > 0) cl[rt].sum = cl[rt].r - cl[rt].l; else cl[rt].sum = cl[rt * 2].sum + cl[rt * 2 + 1].sum; } // 建树 void build(int rt, int l, int r) { if (r - l > 1) { cl[rt].l = s[l]; cl[rt].r = s[r]; build(rt * 2, l, (l + r) / 2); build(rt * 2 + 1, (l + r) / 2, r); pushup(rt); } else { cl[rt].l = s[l]; cl[rt].r = s[r]; cl[rt].sum = 0; } return; } // 更新 void update(int rt, double y1, double y2, int flag) { if (cl[rt].l == y1 && cl[rt].r == y2) { lazy[rt] += flag; pushup(rt); return; } else { if (cl[rt * 2].r > y1) update(rt * 2, y1, min(cl[rt * 2].r, y2), flag); if (cl[rt * 2 + 1].l < y2) update(rt * 2 + 1, max(cl[rt * 2 + 1].l, y1), y2, flag); pushup(rt); } } int main() { int temp = 1, n; double x1, y1, x2, y2, ans; while (scanf("%d", &n) && n) { ans = 0; for (int i = 0; i < n; i++) { scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2); p[i].x = x1; p[i].y1 = y1; p[i].y2 = y2; p[i].flag = 1; p[i + n].x = x2; p[i + n].y1 = y1; p[i + n].y2 = y2; p[i + n].flag = -1; s[i + 1] = y1; s[i + n + 1] = y2; } sort(s + 1, s + (2 * n + 1)); // 离散化 sort(p, p + 2 * n, cmp); // 把矩形的边的横坐标从小到大排序 build(1, 1, 2 * n); // 建树 memset(lazy, 0, sizeof(lazy)); update(1, p[0].y1, p[0].y2, p[0].flag); for (int i = 1; i < 2 * n; i++) { ans += (p[i].x - p[i - 1].x) * cl[1].sum; update(1, p[i].y1, p[i].y2, p[i].flag); } printf("Test case #%d\nTotal explored area: %.2lf\n\n", temp++, ans); } return 0; }

本版实现的关键差异在于：

• cl[rt].l / cl[rt].r直接存储离散化后的原始坐标值，而非下标，pushup中覆盖长度直接用cl[rt].r - cl[rt].l计算，避免坐标到下标的反复映射；
• 支持多组测试数据（while (scanf("%d", &n) && n)），输出带Test case编号与保留两位小数的面积；
• update递归时用min/max裁剪区间，保证与节点管理区间精确匹配，从而正确维护lazy标记。

矩形面积并练习

• POJ 1177「Picture」
• POJ 3832「Posters」
• 洛谷 P1856 [IOI1998] [USACO5.5] 矩形周长 Picture，练习提示：
  • 横边贡献就是覆盖长度变化量；
  • 两个方向分别算一次可以避免竖直边的讨论；
  • 操作排序时注意考虑两个矩形边重合的情况；
  • 数据范围允许时，不用线段树直接平方时间模拟即可。

B 维正交范围

定义：B 维正交范围指在 B 维直角坐标系下，第 $i$ 维坐标落在整数范围 $[l_i, r_i]$ 内的点集。通常：

• 一维正交范围简称区间；
• 二维正交范围简称矩形；
• 三维正交范围简称立方体。

我们常说的二维数点就是二维正交范围查询。

对于静态的二维问题，通用策略是：用扫描线扫一维，用数据结构维护另一维。扫描线从左到右扫的过程中，会在数据结构维护的那一维上产生一些修改与查询：

• 如果查询的信息可差分，直接使用差分（一般用树状数组或线段树维护；因为树状数组好写且常数小，多数选手优先选择树状数组）；
• 如果查询不可差分，则需要使用分治，典型是 CDQ 分治（本文不展开分治部分）。

另一种更易理解的视角是站在序列角度而非二维平面角度：扫描线实际上是枚举右端点 $r = 1 \cdots n$，维护一个数据结构，支持对任意给定的 $l$ 查询"$l$ 到 $r$ 的答案是什么"。即扫描线扫询问右端点，数据结构维护所有左端点的答案——遍历一维，数据结构维护另一维。此类问题的时间复杂度一般为 $O((n + m)\log n)$。

二维数点

问题描述：给一个长为 $n$ 的序列，有 $m$ 次查询，每次查询区间 $[l, r]$ 中值落在 $[x, y]$ 内的元素个数。

这个问题被称为二维数点。可以证明它等价于查询一个二维平面内矩形区域中的点数：把序列位置看作横坐标、值看作纵坐标，则区间 $[l,r]$ 中值在 $[x,y]$ 内的元素正是横坐标在 $[l,r]$、纵坐标在 $[x,y]$ 的矩形内的点。

最简单的处理方法是扫描线 + 树状数组：静态二维问题经扫描线转换为动态一维问题，动态一维问题由树状数组维护。

具体流程（注意这里"枚举"的是横坐标即序列下标）：

1. 将所有询问与点坐标离散化；
2. 用树状数组维护权值（值域）；
3. 对于每次询问的 $l$ 和 $r$，在枚举到 $l-1$ 时统计当前位于 $[x,y]$ 内的数的数量 $a$，继续枚举到 $r$ 时统计当前位于 $[x,y]$ 内的数量 $b$，则$b - a$即为该次询问的答案。

这里的 $a$、$b$ 之所以可差分，是因为树状数组回答的是"前缀 $[1, k]$ 内满足值域条件的个数"，两个前缀相减即得区间答案。

例题一：洛谷 P2163 [SHOI2007] 园丁的烦恼

题目即经典的静态二维数点。参考代码 scanning_3.cpp 的思路：

设左下角为 $(0,0)$、右上角为 $(x,y)$ 的矩形内包含 $ans_{x,y}$ 个点，则一次矩形询问可以被差分为：

$$ans_{c,d} - ans_{a-1,d} - ans_{c,b-1} + ans_{a-1,b-1}$$

实现时将每个差分项视为一个ope操作（type=1加贡献、type=2减贡献），与type=0的加点操作一起按横坐标排序后一次性扫描：

#include <algorithm> #include <iostream> int n, m; int x[500010], y[500010], ans[500010]; int ax[1500010], ay[1500010], tx, ty; // 离散化 struct query { int a, b, c, d; } q[500010]; // 保存查询操作方便离散化 struct ope { int type, x, y, id; ope(int type = 0, int x = 0, int y = 0, int id = 0) { this->type = type, this->x = x, this->y = y, this->id = id; } bool operator<(const ope& rhs) const { if (x == rhs.x) return type < rhs.type; return x < rhs.x; } }; ope op[2500010]; int tot; // 操作总数 int sum[1500010]; // 树状数组 int lowbit(int x) { return x & (-x); } void add(int x, int k) { while (x <= 1500000) { sum[x] = sum[x] + k; x = x + lowbit(x); } } int getsum(int x) { int ret = 0; while (x > 0) { ret = ret + sum[x]; x = x - lowbit(x); } return ret; } using std::cin; using std::cout; int main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> m, tx = n, ty = n; for (int i = 1; i <= n; i++) cin >> x[i] >> y[i], ax[i] = x[i], ay[i] = y[i]; for (int i = 1, l, r; i <= m; i++) { cin >> q[i].a >> q[i].b >> q[i].c >> q[i].d; ax[++tx] = q[i].a, ay[++ty] = q[i].b, ax[++tx] = q[i].c, ay[++ty] = q[i].d; } std::sort(ax + 1, ax + tx + 1), std::sort(ay + 1, ay + ty + 1); tx = std::unique(ax + 1, ax + tx + 1) - ax - 1; ty = std::unique(ay + 1, ay + ty + 1) - ay - 1; for (int i = 1; i <= n; i++) { x[i] = std::lower_bound(ax + 1, ax + tx + 1, x[i]) - ax; y[i] = std::lower_bound(ay + 1, ay + ty + 1, y[i]) - ay; op[++tot] = ope(0, x[i], y[i], i); // 加点操作 } for (int i = 1; i <= m; i++) { q[i].a = std::lower_bound(ax + 1, ax + tx + 1, q[i].a) - ax; q[i].b = std::lower_bound(ay + 1, ay + ty + 1, q[i].b) - ay; q[i].c = std::lower_bound(ax + 1, ax + tx + 1, q[i].c) - ax; q[i].d = std::lower_bound(ay + 1, ay + ty + 1, q[i].d) - ay; op[++tot] = ope(1, q[i].c, q[i].d, i); // 将查询差分 op[++tot] = ope(1, q[i].a - 1, q[i].b - 1, i); op[++tot] = ope(2, q[i].a - 1, q[i].d, i); op[++tot] = ope(2, q[i].c, q[i].b - 1, i); } std::sort(op + 1, op + tot + 1); // 将操作按横坐标排序，且优先执行加点操作 for (int i = 1; i <= tot; i++) { if (op[i].type == 0) add(op[i].y, 1); else if (op[i].type == 1) ans[op[i].id] += getsum(op[i].y); else ans[op[i].id] -= getsum(op[i].y); } for (int i = 1; i <= m; i++) cout << ans[i] << '\n'; return 0; }

实现细节：ope的比较运算符保证横坐标相同时加点操作（type=0）优先于查询操作，从而正确处理"当前横坐标上的点是否计入该位置查询"的边界。仓库自带的测试数据 scanning_3.in 中，3 个点 $(0,0)、(0,1)、(1,0)$ 查询矩形 $(0,0)-(1,1)$，期望输出 scanning_3.ans 为3。

例题二：洛谷 P1908 逆序对

逆序对同样可以用扫描线思维解决。参考代码 scanning_4.cpp：

将求逆序对个数转化为从后向前枚举每个位置 $i$，求在区间 $[i+1,n]$ 中、大小在 $[0,a_i]$ 内的点的个数。题目数据范围可达 $10^9$，因此先离散化；然后从后向前遍历数组，每遍历到一个数就把它加入树状数组（单点修改），随后统计当前一共有多少个数小于当前枚举的数——由于是从后向前遍历，比当前值小的数的个数恰好就是它的逆序对个数。整个过程是"单点修改 + 区间查询"的标准树状数组应用：

#include <algorithm> #include <iostream> using ll = long long; using namespace std; struct node { ll data; ll num; } f[500010]; ll n, ans, a[500010]; bool cmp(node a, node b) { if (a.data == b.data) { return a.num < b.num; } return a.data < b.data; } ll sum[500010]; int lowbit(int x) { return x & (-x); } void add(int x, int k) { while (x <= n) { sum[x] = sum[x] + k; x = x + lowbit(x); } } int getsum(int x) { int ret = 0; while (x > 0) { ret = ret + sum[x]; x = x - lowbit(x); } return ret; } int main() { cin >> n; for (ll i = 1; i <= n; i++) { cin >> f[i].data; f[i].num = i; } sort(f + 1, f + 1 + n, cmp); for (int i = 1; i <= n; i++) { a[f[i].num] = i; } for (ll i = n; i > 0; i--) { ans += getsum(a[i]); add(a[i], 1); } cout << ans; return 0; }

这里先对data排序并将原下标映射为离散化后的排名a[i]，再倒序扫描：getsum(a[i])统计的是已插入的、排名小于等于a[i]的元素个数。因为相等元素（相同值）不构成逆序对，所以对相同值的元素也要排序后赋予不同排名，才能保证严格"小于"的计数。

例题三：洛谷 P1972 [SDOI2009] HH 的项链

简要题意：给定一个序列，多次询问区间 $[l,r]$ 中有多少种不同的数。

这类问题可以推导性质后使用扫描线枚举所有右端点、数据结构维护每个左端点的答案；也可以转换到二维平面，变成一个矩形查询问题。参考代码 scanning_5.cpp 采用后者：

1. 设 $pre_i$ 为 $a_i$ 上一次出现的位置，若未出现过则 $pre_i = 0$；
2. 如果一种数在区间内出现多次，只应产生一次贡献。不妨认为每种数的贡献记在区间中第一次出现的位置上，此时可证明：总贡献即为满足 $pre_x \le l-1$ 的个数（反证法易证）；
3. 于是问题变成：给定序列 $pre$，多次查询区间 $[l,r]$ 中有多少个 $pre_i \le l-1$；
4. 把每个 $pre_i$ 看作二维平面上的点：$i$ 是横坐标，$pre_i$ 是纵坐标，问题就转化为二维数点——每次询问左下角为 $(l,0)$、右上角为 $(r,l-1)$ 的矩形内点数。

该询问可差分：拆成左下角 $(0,0)$、右上角 $(r,l-1)$ 的矩形点数减去左下角 $(0,0)$、右上角 $(l-1,l-1)$ 的矩形点数，从而方便用扫描线处理：

#include <algorithm> #include <iostream> int n, m, a[1000010], ans[1000010]; int pre[1000010], lst[1000010]; // 处理 pre struct ope { int type, x, y, id; ope(int type = 0, int x = 0, int y = 0, int id = 0) { this->type = type, this->x = x, this->y = y, this->id = id; } bool operator<(const ope& rhs) const { if (x == rhs.x) return type < rhs.type; return x < rhs.x; } }; ope op[2500010]; int tot; // 操作总数 int sum[1000010]; // 树状数组 int lowbit(int x) { return x & (-x); } void add(int x, int k) { x++; // 位置 0 也要进行修改，所以树状数组下标均加 1 while (x <= n) { sum[x] = sum[x] + k; x = x + lowbit(x); } } int getsum(int x) { x++; int ret = 0; while (x > 0) { ret = ret + sum[x]; x = x - lowbit(x); } return ret; } using std::cin; using std::cout; int main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; pre[i] = lst[a[i]], lst[a[i]] = i; // 处理 pre op[++tot] = ope{0, i, pre[i], i}; // 加点操作 } cin >> m; for (int i = 1, l, r; i <= m; i++) { cin >> l >> r; op[++tot] = ope{1, r, l - 1, i}; // 将查询差分 op[++tot] = ope{2, l - 1, l - 1, i}; } std::sort(op + 1, op + tot + 1); // 将操作按横坐标排序，且优先执行加点操作 for (int i = 1; i <= tot; i++) { if (op[i].type == 0) add(op[i].y, 1); else if (op[i].type == 1) ans[op[i].id] += getsum(op[i].y); else ans[op[i].id] -= getsum(op[i].y); } for (int i = 1; i <= m; i++) cout << ans[i] << '\n'; return 0; }

需要注意：因为 $pre_i$ 可以为 $0$，树状数组的add与getsum内部对所有下标+1，避免对位置 $0$ 的修改丢失。单次操作复杂度 $O(\log n)$，共 $n$ 次加点与 $2m$ 次查询，总时间复杂度 $O((n + m)\log n)$。

二维数点练习

• 洛谷 P8593「KDOI-02」一个弹的投：逆序对的应用；
• AcWing 4709. 三元组：上一题的弱化版，同样为逆序对应用；
• 洛谷 P8773 [蓝桥杯 2022 省 A] 选数异或：HH 的项链魔改版；
• 洛谷 P8844 [传智杯 #4 初赛] 小卡与落叶：树上问题转序列问题后进行二维数点。

总而言之，二维数点的主要思路就是：数据结构维护一维，然后枚举另一维。

总结：扫描线的统一框架

回顾全文，扫描线算法可以归纳为统一的四步框架：

1. 建模：把目标几何问题（面积并 / 数点 / 周长）转化为"扫描一维 + 维护另一维"的序列问题；
2. 离散化：将参与修改与查询的坐标排序去重，映射为紧凑下标（整数坐标可直接用lower_bound，浮点坐标需注意区间表示）；
3. 扫描：把点、矩形边、差分后的询问统一打包成操作，按扫描方向排序，并用 type 保证同坐标下修改先于查询；
4. 维护：区间覆盖问题用线段树（维护覆盖次数v与覆盖长度w），可差分的前缀查询用树状数组。

无论是矩形面积并还是二维数点，其复杂度均为 $O((n+m)\log n)$，区别只在于数据结构的选择与操作的可差分性。掌握这一框架后，逆序对、HH 的项链、矩形周长等经典问题都可以统一到扫描线视角下解决。

仓库内相关资源

• 本文核心文档：docs/geometry/scanning.md
• 扫描线参考代码目录：docs/geometry/code/scanning/
• 扫描线测试数据目录：docs/geometry/examples/scanning/
• 离散化前置知识：docs/misc/discrete.md
• 计算几何章节索引：docs/geometry/index.md
• 分治（CDQ 分治）进阶阅读：docs/misc/cdq-divide.md

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki