老李的牧场里钉着几十根高低不一的木桩，他想用一卷弹性极好的橡皮筋把所有木桩都套住。松手之后，橡皮筋自动绷紧，围出一块既不漏掉任何木桩、又占地最小的土地——这块地的边界，就是数学家口中的“凸包”。后来老李又在牧场里盖了几间矩形牛棚，他想知道棚顶真正遮住了多少地面，可牛棚彼此重叠，直接相加会重复计算。老李干脆取来一把大扫帚，从牧场最左边缓缓推到最右边：每路过一条棚边就停下来，在账本上记下“此刻头顶被棚布遮住的总宽度”，再乘上扫帚刚刚推过的距离，一段一段累加。这把扫帚就是扫描线算法，那张分层记账的账本则演化成线段树。本文用这个牧场故事，带你从橡皮筋到扫帚，吃透凸包（Graham 扫描与 Andrew 单调链）与扫描线（矩形面积并、周长并）两大算法体系，并看清它们的复杂度与工程用法。

岗位关联

计算几何是 AI 视觉、路径规划、区间统计等应用的地基。掌握凸包与扫描线，等于拿到从几何模型到高效工程的直通钥匙，是算法工程师进阶的硬核分水岭。

目录
  1. 可视化演示
  2. 凸包基础：橡皮筋的数学
  3. Graham扫描：绕圈走，见右转就退
  4. Andrew单调链：两趟直走搭上下壳
  5. 扫描线原理：大扫帚的事件账本
  6. 矩形面积并：重叠只算一次
  7. 矩形周长并：彩灯只拉轮廓
  8. 线段树维护：分层货架账本
  9. 工程与复杂度：工具的保养与适用
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

凸包是计算几何的基础问题，Graham扫描与Andrew单调链是经典解法。本文还讲解扫描线法求矩形面积并与周长... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

凸包定义与G：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

凸包基础：橡皮筋的数学

老李把橡皮筋往木桩堆上一套，松手后它自动绷成一个“无处凹陷”的多边形：所有木桩都被包在里面，任何一个顶点处拐弯的方向都保持一致，没有哪个角是凹进去的。这个被橡皮筋逼出来的多边形，就是所有木桩的“凸包”。更严谨地说，凸包是包含全部点的最小凸多边形——只要还有一点凹进去，就说明还有收缩空间，橡皮筋还会继续绷紧。

要把“凹进去”变成程序能判断的条件，需要一把“转向灯”——叉积。想象你在木桩 A 的位置，正沿着 A→B 的方向走，前方 C 是下一个目标。把 A→B 和 A→C 看成两条有方向的线段，叉积就告诉你该向左打方向盘还是向右打：结果为正说明是左转（逆时针），为负说明是右转（顺时针），为零则三点在一条直线上。这就是叉积的转向判定。

叉积的计算公式如下：

有了转向灯，还差一张“环形名单”：以最低的木桩为圆心，把其余木桩按“从圆心看过去的方位角”从小到大排成一圈，这叫极角排序。这样老李就能按顺序绕着木桩走，每到一个岔路口都看一眼转向灯，判断该不该拐弯。整个凸包算法的地基，就这样由橡皮筋、转向灯和环形名单三样东西铺好了。

cross(P1,P2,P3)=(x2−x1)(y3−y1)−(y2−y1)(x3−x1)\displaystyle \text{cross}(P_1, P_2, P_3) = (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)
三个点的横纵坐标交叉相乘再相减，得到的正负号就是“转向灯”的颜色。
  1. 基准点$P_1$ 是判定转向的基准点，相当于橡皮筋当前所在的那根木桩。
    P1=(x1,y1)P_1 = (x_1, y_1)
  2. 两个位移向量$\overrightarrow{P_1P_2}$ 是已经走过来的方向，$\overrightarrow{P_1P_3}$ 是打算拐过去的方向。
    P1P2→=(x2−x1, y2−y1),P1P3→=(x3−x1, y3−y1)\overrightarrow{P_1P_2} = (x_2 - x_1,\ y_2 - y_1), \quad \overrightarrow{P_1P_3} = (x_3 - x_1,\ y_3 - y_1)
  3. 叉积展开两个向量“外积”的 z 分量，即交叉相乘再相减。
    (x2−x1)(y3−y1)−(y2−y1)(x3−x1)(x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)
  4. 符号判向大于 0 是左转，小于 0 是右转，等于 0 是三点共线。
    cross>0⇒左转,cross<0⇒右转\text{cross} > 0 \Rightarrow \text{左转}, \quad \text{cross} < 0 \Rightarrow \text{右转}

Graham扫描：绕圈走，见右转就退

老李决定真正动手围栅栏。他的办法很朴素：先走到牧场最低处那根木桩（最左下）蹲下来，把橡皮筋的一头拴在它身上，然后按环形名单的顺序，一根一根绕着走，每遇到一根木桩就把它拉进围栏候选名单。

问题是，有时候拉进新木桩后，橡皮筋会突然“走过头”，形成右转。这时候老李会回头看一眼：如果最后三根木桩构成右转，说明中间那根木桩是多余的，橡皮筋会把它压到内部去，于是果断退回去，把中间那根从名单上划掉，再继续检查新的最后三根。这个“退一步”的动作在程序里叫“出栈”，不断回退直到只剩下左转为止。整个过程中，每一根木桩最多被拉进来一次、被划掉一次，所以除了排序之外，剩下的工作是线性的。

出栈的判定条件用叉积写作：

Graham 扫描的第一步是排序，用 O(n log n) 的时间把所有点按极角排好；之后每个点至多入栈一次、出栈一次，总共 O(n)。所以整体复杂度就是 O(n log n)。老李围着木桩绕了一圈，左转就继续走，右转就退回去重新选路，最后留在名单上的，恰好就是橡皮筋会绷到的所有顶点。

cross(Sk−1,Sk,pi)≤0⇒弹出 Sk\displaystyle \text{cross}(S_{k-1}, S_k, p_i) \le 0 \Rightarrow \text{弹出 } S_k
当前栈顶附近三点不再是左转时，就说明栈顶那根木桩会被橡皮筋包进内部，直接丢弃。
  1. 栈顶附近两点$S_{k-1}$ 与 $S_k$ 是当前已确定围栏的最后两段转角，记录在栈里。
    Sk−1,Sk∈stackS_{k-1}, S_k \in \text{stack}
  2. 当前候选点$p_i$ 是按极角序新遇到的木桩，打算把它拉进围栏。
    pi∈orderp_i \in \text{order}
  3. 转向判定$\text{cross}(S_{k-1}, S_k, p_i) \le 0$ 说明从 $S_k$ 走向 $p_i$ 是右转或直行。
    cross(Sk−1,Sk,pi)≤0\text{cross}(S_{k-1}, S_k, p_i) \le 0
  4. 回退操作弹出 $S_k$ 后，用新的栈顶重新检查，直到最后三点满足左转。
    stack.pop(),继续检查新栈顶\text{stack.pop()}, \quad \text{继续检查新栈顶}

Andrew单调链：两趟直走搭上下壳

老李的儿子小李觉得绕圈太容易头晕，提出一个更省脑子的走法：不按角度转圈，而是把所有木桩按“先横坐标、再纵坐标”排成一条直线队，然后从左到右走一趟，只保留“贴着地面”的下边界转角；再从右到左走一趟，只保留“顶着天”的上边界转角。两趟走完，把两条链子首尾一接，就是完整的凸包。这就是 Andrew 单调链算法。

这个算法和 Graham 长得几乎一模一样，唯一的区别是排序方式：Graham 用极角排序（要算反正切，浮点误差大），Andrew 只按坐标排序（只比较大小，误差小、好实现）。判定转向时用的叉积条件完全不变。正因为实现简单、精度更稳，Andrew 单调链在实际工程中更常被采用。

下凸壳的维护条件同样是“非左转就出栈”：

小李的两趟直走，一趟贴地、一趟贴天，正好把橡皮筋的上下两半分别拉了出来。相比绕圈的 Graham，它的优势就像“沿着围墙走直线标点”而不是“绕着柱子转圈看角度”——更稳、更不容易算错方向，也因此成了许多竞赛和工业代码里的首选实现。

cross(Hk−1,Hk,pi)≤0⇒Hk 出栈\displaystyle \text{cross}(H_{k-1}, H_k, p_i) \le 0 \Rightarrow H_k \text{ 出栈}
建下壳时从左往右扫描，碰到右转就把上一个点扔掉；建上壳时从右往左再来一遍。
  1. 坐标排序把点集按照 $(x, y)$ 升序排列，保证扫描方向严格从左到右。
    p1.x<p2.x<⋯<pn.xp_1.x < p_2.x < \dots < p_n.x
  2. 下凸壳 lower顺序遍历排序后的点，用叉积维护左转，得到下边界序列。
    lower=[… ],cross≤0⇒pop\text{lower} = [\dots], \quad \text{cross} \le 0 \Rightarrow \text{pop}
  3. 上凸壳 upper逆序遍历同一份有序点列，再次用叉积维护左转，得到上边界。
    upper=scan(pn,pn−1,…,p1)\text{upper} = \text{scan}(p_n, p_{n-1}, \dots, p_1)
  4. 去重拼接两条链的首尾是同一个点，各去掉最后一个元素再相连。
    H=lower[0..k−2]+upper[0..m−2]H = \text{lower}[0..k-2] + \text{upper}[0..m-2]

扫描线原理：大扫帚的事件账本

圈完地，老李又遇到了新麻烦：牧场里盖了几间矩形牛棚，他想知道棚顶总共遮住了多少地面。他取出那把大扫帚，从牧场最左边开始，缓缓向右推。聪明的老李发现，扫帚只有经过牛棚的“左竖边”或“右竖边”时，头顶的遮挡情况才会变化；在两条竖边之间，头顶一直不变，完全可以一口气推过去。于是他把所有竖边按横坐标排好队，扫帚只在这些“事件点”停靠——这就是事件驱动思想。

每次停靠要做两件事：一是更新账本，遇到左竖边就给对应高度区间“盖一层布”（记 +1），遇到右竖边就“掀一层布”（记 -1）；二是结算，用“本次停靠到下次停靠的距离”乘以“当前被遮住的总高度”，记入面积。这里“当前被遮住的总高度”是并集后的长度，重叠的棚布只算一份，绝不重复。

由于牛棚的横纵坐标可能很稀疏，老李把所有的 y 坐标收集起来排序、去重，只保留这些“关键高度”之间的区间，这个过程叫坐标离散化。离散化之后，事件的数量从“无限多个坐标”压缩成 O(n) 个区间，扫帚才能高效地一路推到底。面积累加的公式是：

扫帚的精神在于“只在变化点停下，不变的路段一口价结算”。这像老李记账时只记“棚布变多/变少的瞬间”，而两瞬间之间的地面，只要头顶情况没变，就放心按同一个高度算。这一思想奠定了后面面积并、周长并的整个框架。

S=∑i=1m−1(xi+1−xi)×hi\displaystyle S = \sum_{i=1}^{m-1} (x_{i+1} - x_i) \times h_i
面积 = 每段路程（相邻事件横坐标之差）× 该段路程上头顶被遮住的总高度，全部路段累加。
  1. 事件横坐标$x_1 < x_2 < \dots < x_m$ 是所有矩形竖边按横坐标排序后的停靠点。
    x1≤x2≤⋯≤xmx_1 \le x_2 \le \dots \le x_m
  2. 路程宽度$x_{i+1} - x_i$ 是扫帚从第 i 次停靠推到第 i+1 次停靠所经过的宽度。
    Δxi=xi+1−xi\Delta x_i = x_{i+1} - x_i
  3. 覆盖高度$h_i$ 是扫帚在 $x_i$ 处处理完事件后，y 方向上被覆盖的并集总长度。
    hi=lencover(xi)h_i = \text{len}_{\text{cover}}(x_i)
  4. 累加求面积每段“宽 × 高”相加，就得到被棚布遮住的总面积。
    S=∑i=1m−1Δxi×hiS = \sum_{i=1}^{m-1} \Delta x_i \times h_i

矩形面积并：重叠只算一次

老李发现牛棚之间有不少重叠：两间棚子的阴影叠在一起，地面上那块被双重遮住的地方，按面积并的规则只能算一次。于是他在账本上多加了一栏“覆盖次数”：每一段 y 区间被几块棚布盖着，就记几。只要某段区间的覆盖次数大于 0，它就算进“当前遮住的总高度”；至于盖了两层还是三层，答案都是同一份地面。

这一招叫“覆盖计数”。每次扫帚停到左竖边，就把对应 y 区间所有离散化段的覆盖次数 +1；停到右竖边就 -1。某个离散化段只要次数大于 0，它的长度就计入总覆盖高度；次数归零，这段就从账本上划掉。这样“高度合并”自然完成：相邻且都被覆盖的区间连成一片，重叠部分自动只算一次。面积累加的公式写作：

老李的记账原则很朴素：同一块地面，不管头顶叠了几层棚布，都只按“有遮阴”记一次。正是这个“覆盖次数只判有无、不计多少”的思路，把重叠这个看似麻烦的问题变成了一个简单的计数游戏。若用线段树维护区间覆盖次数，每次事件更新 O(log n)，总面积便在 O(n log n) 时间内算完。

S=∑i=1m−1(xi+1−xi)×lencover(xi)\displaystyle S = \sum_{i=1}^{m-1} (x_{i+1} - x_i) \times \text{len}_{\text{cover}}(x_i)
把上节的 $h_i$ 明确为“覆盖并集的总长度”：同一高度被多个矩形盖住时，长度只贡献一次。
  1. 覆盖长度$\text{len}_{\text{cover}}(x_i)$ 表示扫帚停在 $x_i$ 时，y 方向上所有“至少被一块棚布盖住”的区间的总长度。
    lencover(xi)=∑cnt(段)>0段长\text{len}_{\text{cover}}(x_i) = \sum_{\text{cnt}(段) > 0} \text{段长}
  2. 只取并集覆盖次数大于 0 的段才计入，重叠的段不重复计长。
    cnt(段)>0⇒该段计入\text{cnt}(段) > 0 \Rightarrow \text{该段计入}
  3. 乘以路程与下一个事件的横坐标差相乘，得到这一段路的遮阴面积。
    (xi+1−xi)×lencover(xi)(x_{i+1} - x_i) \times \text{len}_{\text{cover}}(x_i)
  4. 全局求和把所有路段的贡献加起来，就是矩形并集的真实面积。
    S=∑iΔxi×lencover(xi)S = \sum_i \Delta x_i \times \text{len}_{\text{cover}}(x_i)

矩形周长并：彩灯只拉轮廓

面积算清了，老李还想沿着所有牛棚的外围拉一圈彩灯，庆祝丰收。彩灯不能拉在牛棚内部的重叠隔墙上，只能沿着整个牧场建筑群的“外轮廓”走。也就是说，要求的是所有矩形并集图形的周长。周长由两类边组成：竖边和横边。

竖边出现在事件发生的竖线上——某间牛棚的左竖边或右竖边暴露在外轮廓上的那一段。扫帚每到一处事件，有的竖边“新出现”（某矩形开始覆盖），有的竖边“消失”（某矩形结束覆盖），把新增和消失的长度分别累计，就是竖边总长。横边则出现在相邻事件之间：每一段连续被覆盖的 y 区间，其上下两条边界都会水平延伸，所以横边的贡献是“连续段数 × 2 × 路程宽”。公式如下：

拉彩灯只看轮廓、不拉隔断，这要求算法同时盯住“覆盖长度”和“连续段数”两个量。前者负责竖边，后者负责横边。实现时常对 x 方向扫一遍统计竖边与横边，必要时再对 y 方向扫一遍交叉验证，两趟“描边”合起来，正好是老李在外墙拉出的那圈灯光。

P竖=∑i(addi+rmi),P横=2∑iki⋅(xi+1−xi)\displaystyle P_{\text{竖}} = \sum_{i} (\text{add}_i + \text{rm}_i), \qquad P_{\text{横}} = 2 \sum_{i} k_i \cdot (x_{i+1} - x_i)
周长分成竖边与横边两部分：竖边在事件处新增与消失，横边按“连续覆盖段的上下两条边”延伸长度计算。
  1. 新增竖边$\text{add}_i$ 是事件 i 处新露出的矩形竖边总长度。
    addi=事件 i 后比之前多出的覆盖长度\text{add}_i = \text{事件 i 后比之前多出的覆盖长度}
  2. 消失竖边$\text{rm}_i$ 是事件 i 处从外轮廓上消失的矩形竖边长度。
    rmi=事件 i 前比之后多出的覆盖长度\text{rm}_i = \text{事件 i 前比之后多出的覆盖长度}
  3. 连续段数$k_i$ 是相邻事件之间，y 方向被覆盖且彼此不连续的区间个数。
    ki=disjoint 覆盖区间数k_i = \text{disjoint 覆盖区间数}
  4. 横边累加每段连续覆盖区间贡献上下两条水平边，长度各为 $\Delta x$。
    P横=2∑iki⋅(xi+1−xi)P_{\text{横}} = 2 \sum_i k_i \cdot (x_{i+1} - x_i)

线段树维护：分层货架账本

事件多的时候，老李的账本渐渐记不过来了：每次停靠都要把一整段 y 区间里的每个小段都翻出来改覆盖次数，太费劲。他灵机一动，把账本改造成一个“分层货架”：根节点管整个 y 范围，左右两个儿子各管一半，再往下分，直到最小的离散化区间放在最底层的格子里。这就是线段树。

每次扫帚停靠，要做的事变成“区间更新”：把 [y1, y2) 范围内的所有格子的覆盖次数 +1 或 -1。如果某个节点的区间被事件完整覆盖，老李就不必拆开每一格逐个改，而是直接在这层货架上贴一张便签（记录覆盖次数 +1），整格封存。这就是懒标记思想：能整层处理就不下钻。特别的是，在求覆盖长度的问题里，我们只关心根节点当前的覆盖总长度，从不需要查询某个具体子区间的长度，所以这个“便签”根本不必下推给儿子。

节点合并长度的规则非常简洁：

老李的货架妙就妙在“整格盖住就贴封条，不拆包数货”。每次事件只需沿着树向下走 O(log n) 层，改动路径上的节点即可，根节点的长度随时可查。于是面积并、周长并的时间都被压缩到 O(n log n)，大牧场也能在一眨眼间扫完。

len(u)={Ru−Lu,cnt(u)>0len(2u)+len(2u+1),cnt(u)=0\displaystyle \text{len}(u) = \begin{cases} R_u - L_u, & \text{cnt}(u) > 0 \\[4pt] \text{len}(2u) + \text{len}(2u+1), & \text{cnt}(u) = 0 \end{cases}
被完整覆盖的节点直接取整段长度；没被完整覆盖的节点，把左右儿子的长度加起来。
  1. 覆盖次数$\text{cnt}(u)$ 记录节点 u 对应的 y 区间被多少个矩形整体覆盖。
    cnt(u)≥0\text{cnt}(u) \ge 0
  2. 整段覆盖当 $\text{cnt}(u) > 0$ 时，整个区间都在阴影里，长度就是区间全长。
    len(u)=Ru−Lu\text{len}(u) = R_u - L_u
  3. 零覆盖当 $\text{cnt}(u) = 0$ 时，说明本层不是整体被盖住，需要问两个儿子。
    len(u)=len(2u)+len(2u+1)\text{len}(u) = \text{len}(2u) + \text{len}(2u+1)
  4. 根节点汇总最终 $\text{len}(1)$ 就是当前 y 方向被覆盖的并集总长度。
    hi=len(1)h_i = \text{len}(1)

工程与复杂度：工具的保养与适用

老李把两件工具——橡皮筋（凸包）和扫帚（扫描线）——放进工具箱，回头一盘点：凸包两兄弟 Graham 与 Andrew 的时间都花在排序上，是 O(n log n)，排序之后每个点至多进出栈一次，线性；扫描线的时间花在事件排序与线段树更新上，同样是 O(n log n)，空间上线段树数组与离散化区间数成正比，是 O(n)。

工程上还有两个保养要点。一是数值精度：叉积里藏着乘法与减法，浮点坐标在极端接近共线时可能误差累积，所以工业实现常把坐标取整或直接用整数运算。二是离散化的开闭习惯：矩形区间通常写成“左闭右开” $[y_1, y_2)$，避免相邻矩形在边界处重复计边。老李的工具箱虽然只有两件宝贝，但擦得亮、用得巧，从 AI 视觉的轮廓提取到芯片版图的密度统计，处处都能派上用场。

T(n)=O(nlog⁡n),S(n)=O(n)\displaystyle T(n) = O(n \log n), \qquad S(n) = O(n)
四种算法（两个凸包、面积并、周长并）的时间和空间开销一致，瓶颈都在排序与对数级更新。
  1. 排序主导Graham/Andrew 的极角或坐标排序、扫描线的事件排序，都是 O(n log n)。
    O(nlog⁡n)=sort(n)+n×O(log⁡n)O(n \log n) = \text{sort}(n) + n \times O(\log n)
  2. 线性处理凸包中每个点常数次入栈出栈；扫描线每个事件一次区间更新。
    O(n) 次基本操作O(n) \text{ 次基本操作}
  3. 对数更新线段树每次区间更新的代价是树高 O(log n)。
    O(log⁡n) / 事件O(\log n) \text{ / 事件}
  4. 线性空间线段树开 4 倍区间数，离散化数组 O(n)，总空间 O(n)。
    S(n)=O(4n)=O(n)S(n) = O(4n) = O(n)

AI 应用场景

目标检测后的轮廓聚拢

阶段：模型后处理与几何规整

解决的问题：语义分割或目标检测模型输出的是成千上万个散点（像素级掩码），直接交付这些散点既臃肿又难以计算面积、朝向等属性。用凸包把散点围成最小外接轮廓，就得到了物体紧凑、稳定的几何表达，像老李用橡皮筋把木桩圈成一块地。

具体案例：仓库机器人抓取场景中，RGB-D 相机检测到货架上散落的纸箱点云，先用凸包求出每个纸箱的顶面轮廓，再计算中心与朝向，规划机械臂抓取姿态。轮廓顶点数从数万个点压缩到几十个，实时性大幅提升。

多任务区间占用的真实统计

阶段：数据工程与资源调度分析

解决的问题：多个训练任务同时申请 GPU 显存、日志分区或时间片，区间彼此重叠，直接累加会严重高估真实占用。扫描线把每个区间看成一条“矩形”，用覆盖计数求并集长度，得到真实占用总量，像老李的扫帚只记“至少一块棚布盖住的宽度”。

具体案例：ML 平台团队统计一周内所有分布式训练任务对显存的峰值占用。每个任务按照起止时间与显存地址段生成一个矩形，用扫描线 + 线段树求出时间-显存平面上的并集面积，精确定位资源瓶颈时段，为扩容决策提供依据。

渲染与版图中的遮挡密度估计

阶段：渲染优化与物理设计验证

解决的问题：游戏 UI 或芯片版图中大量矩形区域互相遮挡，需要知道“实际可见/实际占用”的面积与轮廓。矩形面积并与周长并正好给出这两个指标，对应老李“算遮阴面积”和“拉彩灯轮廓”两件事。

具体案例：渲染引擎在做遮挡剔除时，把视口中的 UI 元素看作矩形集合，用面积并计算实际被绘制的像素占比，自动决定哪些层可以合并为一张纹理；芯片物理设计中，用周长并估算各金属层的绕线周长，评估制造良率。

Python 演示

python63 行
def cross(o, a, b):    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])  def convex_hull(pts):    pts = sorted(set(pts))    if len(pts) <= 1:        return pts    lower = []    for p in pts:        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:            lower.pop()        lower.append(p)    upper = []    for p in reversed(pts):        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:            upper.pop()        upper.append(p)    return lower[:-1] + upper[:-1]  def area_union(rects):    xs = sorted(set(x for r in rects for x in (r[0], r[2])))    ys = sorted(set(y for r in rects for y in (r[1], r[3])))    events = []    for x1, y1, x2, y2 in rects:        events.append((x1, 1, y1, y2))        events.append((x2, -1, y1, y2))    events.sort()    n = len(ys) - 1    cnt = [0] * (4 * n)    length = [0.0] * (4 * n)     def update(node, l, r, ql, qr, val):        if qr <= l or r <= ql:            return        if ql <= l and r <= qr:            cnt[node] += val        else:            mid = (l + r) // 2            update(node * 2, l, mid, ql, qr, val)            update(node * 2 + 1, mid, r, ql, qr, val)        if cnt[node]:            length[node] = ys[r] - ys[l]        else:            length[node] = (length[node * 2] + length[node * 2 + 1]                            if r - l > 1 else 0.0)     area = 0.0    for i in range(len(events) - 1):        _, tag, y1, y2 = events[i]        l = ys.index(y1)        r = ys.index(y2)        update(1, 0, n, l, r, tag)        area += (events[i + 1][0] - events[i][0]) * length[1]    return area  if __name__ == '__main__':    pts = [(0, 0), (1, 2), (2, 1), (3, 3), (1, 1), (2, 0), (0, 2)]    print('Andrew 凸包:', convex_hull(pts))    rects = [(0, 0, 4, 3), (2, 1, 6, 5), (5, 0, 7, 2)]    print('矩形面积并:', area_union(rects))
目的：用 Andrew 单调链求点集凸包，再用“扫描线 + 覆盖计数线段树”求多个矩形的面积并，演示本文两大算法体系的完整实现。
  1. def cross(o, a, b):叉积函数，三个点返回转向符号，是凸包与扫描线共同的“转向灯”。
  2. while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:下凸壳维护：非左转就把栈顶弹出，对应老李“见右转就退”。
  3. return lower[:-1] + upper[:-1]去掉两链重复的首尾点再拼接，得到完整凸包。
  4. events.append((x1, 1, y1, y2))矩形左竖边记为“覆盖开始”事件，tag 为 +1。
  5. if cnt[node]: length[node] = ys[r] - ys[l]节点被完整覆盖时，长度直接取区间全长，不必看儿子。
  6. area += (events[i + 1][0] - events[i][0]) * length[1]每段路程 × 根节点覆盖总长度，累加出并面积。

常见误区

误区我以为凸包就是把看起来在边缘的点用直线一连就行，不用管顺序，连完之后哪怕中间凹进去也没关系，反正最外面的点都连上了。

正解连线顺序错了会出现边“切进”点集内部，甚至产生自交图形。凸包要求结果必须是凸的，必须按极角或坐标顺序扫描，并用叉积保证每一步都是同向转弯（比如统一左转），凹进去的顶点会被弹出。就像橡皮筋，它自动绷到最外圈，任何凹点都会被拉平，绝不是随便连一圈。

为何常见：“外围”是生活直觉，而算法需要严格的转向判定与处理顺序，初学者容易把几何直观误当成现成的算法。

误区出栈条件写成 `cross <= 0` 会不会把正常的凸包顶点也弹掉？我觉得应该用 `< 0` 才更安全，结果要么多一堆边上的点，要么少点。

正解两者都能得到合法凸包，区别只在是否保留共线点。用 <= 0 会把共线点弹掉，得到“最简凸包”（顶点数最少）；用 < 0 会保留边上的共线点，凸包边上多出若干顶点。选哪个取决于需求：求最小顶点数用前者，要求严格描出所有边界点用后者。

为何常见：教程通常直接写 <= 0，很少解释它与 < 0 的差别，学生看到“弹出合法点”就误以为写错了。

误区扫描到某段路时，把每个矩形的高度加起来，再乘以这段路的宽度，不就算出这段路的遮阴面积了吗？重叠部分多算一点也没关系吧。

正解重叠部分会成倍虚增。正确做法是维护“覆盖并集”的总长度：离散化后对每个 y 小区间记录覆盖次数，只有次数大于 0 的段才计入长度。这就像老李的账本只记“头顶有多少宽度被至少一块棚布盖着”，而不是把所有棚布的宽度全部相加。

为何常见：因为“每段路 × 当前覆盖高度”长得极像矩形面积公式，初学者容易把“对矩形逐个求高求和”与“求覆盖并集长度”混为一谈。

误区线段树区间更新肯定要把标记 push_down 到叶子，否则儿子的长度不准确，根节点的长度也会跟着错。我之前写扫描线面积并时每步都下推，结果又慢又容易写错。

正解在扫描线覆盖长度问题中，我们只查询根节点的 len，从不查询任意子区间的长度。节点只要 cnt > 0，len 直接取整段长度，根本不需要看儿子；cnt = 0 时才用儿子的 len 汇总。所以标记不必下推，cnt 本身就充当了“懒标记”。这是“只查根”与“任意区间查询”的本质区别。

为何常见：多数人先学的是带 push_down 的区间加法线段树，形成“更新必须下推”的惯性，没意识到查询范围只有根节点时，标记可以留在原地、按需汇总。

面试题

Q1. 关于凸包的定义，下列说法正确的是？

单选题 · easy

  • A.连接所有点的边长之和最小的多边形
  • B.包含所有点的最小凸多边形← 正确答案
  • C.包含所有点的最大凸多边形
  • D.任意连接所有外围点的多边形

答案：B。凸包是包含全部点的最小凸多边形，相当于老李的橡皮筋绷紧后的形状。A 强调“边长最小”不准确；C 方向反了；D 忽略凸性与最小性。只有 B 同时满足“包含全部点”和“最小凸”两个条件。

Q2. 叉积 cross(A, B, C) 的结果大于 0 时，从 A 到 B 再到 C 的转向是？

单选题 · easy

  • A.右转（顺时针）
  • B.直行
  • C.左转（逆时针）← 正确答案
  • D.无法确定

答案：C。叉积大于 0 对应向左转，也就是逆时针方向，像转向灯亮起“左拐”。小于 0 才是右转，等于 0 是直行或共线。

Q3. Graham 扫描算法的第一步通常需要做什么？

单选题 · easy

  • A.随机选取任意一点作为起点
  • B.选取最低（最左下）点作为起点，其余点按极角排序← 正确答案
  • C.将所有点按纵坐标从大到小排序
  • D.先求出所有点的几何中点

答案：B。Graham 扫描先选最左下的点作起点，再按极角排序，得到老李绕圈走的“环形名单”。随机起点无法保证扫描方向一致；按纵坐标排序和求中点都不符合算法流程。

Q4. Graham 扫描中，当 cross（栈顶前一个点，栈顶点，当前点） ≤ 0 时，正确的操作是？

单选题 · mid

  • A.将当前点直接入栈
  • B.将栈顶点弹出，并用新的栈顶继续检查← 正确答案
  • C.跳过当前点不再处理
  • D.清空整个栈重新开始

答案：B。叉积不大于 0 说明出现右转或共线，栈顶点会被橡皮筋包进内部，必须弹出，再检查新栈顶是否满足左转，直到条件成立才把当前点入栈。A 会留下凹点，C 会漏点，D 破坏已构建的围栏。

Q5. 与 Graham 扫描相比，Andrew 单调链的主要优点是？

单选题 · mid

  • A.不需要计算叉积
  • B.不需要极角排序，只需按坐标排序，浮点误差更小← 正确答案
  • C.时间复杂度更低
  • D.可以处理任意多边形的面积

答案：B。Andrew 只是把“极角排序”换成“坐标排序”，叉积照用，复杂度同样是 O(n log n)。它避免计算反正切，精度更稳、实现更简单。C 说复杂度更低是错的，D 与凸包无关。

Q6. 扫描线求矩形面积并时，两个相邻事件之间的面积等于？

单选题 · mid

  • A.事件间隔 × 当前所有矩形高度之和
  • B.事件间隔 × 当前覆盖并集的总长度← 正确答案
  • C.当前覆盖并集的总长度
  • D.事件间隔 × 矩形个数

答案：B。相邻事件之间覆盖状态不变，面积 = 路程宽 × 覆盖并集的 y 总长度。A 会重复计算重叠高度；C 漏掉宽度；D 与覆盖情况无关。

Q7. 在线段树维护“覆盖长度”的过程中，下列说法正确的有？

多选题 · mid

  • A.覆盖次数 cnt 表示该区间被多少个矩形完整覆盖← 正确答案
  • B.当 cnt > 0 时，len 取该节点区间的完整长度← 正确答案
  • C.当 cnt = 0 时，len 取左右儿子 len 之和← 正确答案
  • D.每次事件都必须把更新下推到所有叶子节点

答案：ABC。cnt 是“整层封条”计数；被完整覆盖就整段算长，否则汇总儿子。因为我们只查根节点长度，标记不必下推，D 是常见误区中的错误做法，既慢又没必要。

Q8. 求矩形并的周长时，扫描线通常需要额外维护哪些信息？

多选题 · mid

  • A.覆盖长度 len← 正确答案
  • B.覆盖次数 cnt← 正确答案
  • C.连续覆盖段数 k← 正确答案
  • D.所有矩形顶点的坐标和

答案：ABC。len 提供竖边变化量，cnt 支撑覆盖判断，k 用于计算横边（每段上下两条边）。顶点坐标和与周长无关，是干扰项。

Q9. 关于凸包算法，下列说法正确的有？

多选题 · hard

  • A.Graham 扫描基于极角排序← 正确答案
  • B.Andrew 单调链通过两趟扫描分别构造上下凸壳← 正确答案
  • C.Graham 扫描与 Andrew 单调链的时间复杂度都是 O(n log n)← 正确答案
  • D.Andrew 单调链需要对点集进行两次排序

答案：ABC。Graham 按极角排序，Andrew 按坐标排序一次后正反各扫一遍，两者排序都是 O(n log n)。D 说“两次排序”是错的，Andrew 只需一次排序，只是遍历了两趟。

Q10. 在坐标范围达 10^9、矩形个数为 10^5 的情况下，求矩形面积并的正确高效做法是？

单选题 · hard

  • A.遍历每个像素统计覆盖次数
  • B.离散化 y 坐标后用线段树维护覆盖长度，配合扫描线求解← 正确答案
  • C.对每个矩形单独算面积再相加
  • D.用覆盖所有矩形的最小外接矩形估算

答案：B。坐标范围巨大无法逐像素，重叠又不能直接相加，估算误差过大。正确做法是离散化 y 坐标，构造事件扫描，线段树维护覆盖长度，整体 O(n log n)，这正是老李“扫帚 + 分层账本”的工程落地。