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((nm)\log n)$ 级别。二维矩形面积并问题问题描述在二维坐标系中给定多个矩形每个矩形由左下角与右上角坐标给出求所有矩形覆盖区域的并集面积。当矩形数量很小时可以暴力枚举每一条竖线切开图形逐块累加但当数据规模变大例如 $n \le 10^5$就必须借助扫描线。算法过程切分用一条从下往上移动的水平线扫描整个图形。每扫过一条水平边图形就被横向切开一次最终整个矩形并集被切成一系列颜色各异的小矩形。每个小矩形的高就是两次扫描之间的竖直距离而它的水平宽度则在不断变化。标记上下边给每个矩形的下边标记为 $1$上边标记为 $-1$。每当扫描线遇到一条水平边就在这条边于横轴上的投影区间上加上对应标记。这个操作与遍历括号序列完全同构——开括号加 $1$、闭括号减 $1$当前区间的权值对应当前扫描位置的深度而权值是否大于 $0$对应当前位置是否位于某个矩形内部即这段区间是否计入小矩形的宽度。累加面积在任意两次相邻水平边之间小矩形可能不止一个的总宽度就是整个数轴上权值大于 $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[2u1]的访问。注意扫描线的修改与查询都发生在离散化后的坐标下标上因此需要先对横坐标做离散化。参考实现一洛谷 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*21]那么线段树需要开 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 -1a[]收集所有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]$ 的矩形内的点。最简单的处理方法是扫描线树状数组静态二维问题经扫描线转换为动态一维问题动态一维问题由树状数组维护。具体流程注意这里枚举的是横坐标即序列下标将所有询问与点坐标离散化用树状数组维护权值值域对于每次询问的 $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操作type1加贡献、type2减贡献与type0的加点操作一起按横坐标排序后一次性扫描#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的比较运算符保证横坐标相同时加点操作type0优先于查询操作从而正确处理当前横坐标上的点是否计入该位置查询的边界。仓库自带的测试数据 scanning_3.in 中3 个点 $(0,0)、(0,1)、(1,0)$ 查询矩形 $(0,0)-(1,1)$期望输出 scanning_3.ans 为3。例题二洛谷 P1908 逆序对逆序对同样可以用扫描线思维解决。参考代码 scanning_4.cpp将求逆序对个数转化为从后向前枚举每个位置 $i$求在区间 $[i1,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 采用后者设 $pre_i$ 为 $a_i$ 上一次出现的位置若未出现过则 $pre_i 0$如果一种数在区间内出现多次只应产生一次贡献。不妨认为每种数的贡献记在区间中第一次出现的位置上此时可证明总贡献即为满足 $pre_x \le l-1$ 的个数反证法易证于是问题变成给定序列 $pre$多次查询区间 $[l,r]$ 中有多少个 $pre_i \le l-1$把每个 $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 初赛] 小卡与落叶树上问题转序列问题后进行二维数点。总而言之二维数点的主要思路就是数据结构维护一维然后枚举另一维。总结扫描线的统一框架回顾全文扫描线算法可以归纳为统一的四步框架建模把目标几何问题面积并 / 数点 / 周长转化为扫描一维维护另一维的序列问题离散化将参与修改与查询的坐标排序去重映射为紧凑下标整数坐标可直接用lower_bound浮点坐标需注意区间表示扫描把点、矩形边、差分后的询问统一打包成操作按扫描方向排序并用 type 保证同坐标下修改先于查询维护区间覆盖问题用线段树维护覆盖次数v与覆盖长度w可差分的前缀查询用树状数组。无论是矩形面积并还是二维数点其复杂度均为 $O((nm)\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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

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

相关推荐

校园奶茶店微信小程序毕业设计：从登录支付到订单管理的全流程实践

系统运维核心指南：从基础设施到自动化工具生态

等保三级数据库合规选型：ECS自建 vs 瑶池RDS核心差异

更多资讯

智能鱼塘溶氧监测系统设计与实现

热管技术原理、计算与工程应用全解析

LeetCode-Go 题解：1208. Get Equal Substrings Within Budget 滑动窗口解法深度解析

基于Python的财务信用分析与评分卡建模全流程解析

SpringBoot+微信小程序流浪动物救助系统：状态流转与并发控制实战

.NET 8 Web API 项目源码设计：从骨架到鉴权与可靠性验证

今日更新

SpacetimeDB C++ 模块库实战：用 C++20 在数据库内构建 WebAssembly 模块

别踩雷！不是所有 AI 写作工具都靠谱，2026 高校认可工具精选

SSM+MySQL幼儿园管理系统源码解析：从部署到优化

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？