设想你是木匠，面前是一块钉满钉子的木板。你拿起一根橡皮筋，把它套在最外圈的钉子上——橡皮筋弹开后勾勒出的轮廓，就是“凸包”。现在你想知道：这堆钉子里，哪两颗相隔最远？如果有一把两片永远平行的长格尺（卡尺），像双手托盘子一样从两侧夹住这块轮廓，然后缓缓转动，你会看到格尺与轮廓的接触点不断“跳岗换班”。每到一个方向，格尺都恰好卡住两个顶点——这对顶点叫“对踵点”。记录格尺转动一圈中读数最大的间隙，就找到了最远点对；记录读数最小的间隙，就得到了最小宽度矩形的高度方向。这就是旋转卡壳：不做两两比较，而是让两把平行格尺绕一圈，用 O(n) 的时间完成测量。

岗位关联

旋转卡壳是计算几何的“瑞士军刀”，掌握它，你就能在碰撞检测、包围盒优化等高价值工程问题中以线性成本解决问题，这是 AI 从业者必备的算法素养。

目录
  1. 可视化演示
  2. 凸包预处理
  3. 对踵点对
  4. 核心思想
  5. 最远点对
  6. 最小矩形
  7. 复杂度分析
  8. 应用场景
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

旋转卡壳利用凸包对踵点在O(n)时间内求解最远点对与最小宽度矩形等问题。本文详解对踵点的判定方法、旋转过程的实... 切换模式查看不同维度。

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

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

凸包预处理

木匠先把橡皮筋套上钉板：橡皮筋被最外圈的钉子撑住，内部那些钉子根本碰不到皮筋。这个“橡皮筋轮廓”就是凸包。旋转卡壳这把格尺要夹的正是这个轮廓——因为最外面的两颗钉子可能最远，被包在里面的点永远不可能是答案。

从数学上看，最远点对的两个端点必然落在凸包上：若某点在凸多边形内部，它到任何点的距离都不会超过“撑住橡皮筋”的某个凸包顶点。因此我们先把散点集压缩成凸包，把候选点从 n 个暴减到凸包顶点数 h 个，而且这些顶点按逆时针围成一圈，天然有序。

判断“橡皮筋往哪边弹”靠的是叉积：对三个连续顶点 A、B、C，叉积的正负能告诉我们从 AB 转向 AC 是左转还是右转，这正是凸包构建（Graham 扫描）的核心判据。

有了这圈有序的“橡皮筋轮廓”，木匠才敢把格尺架上——下一节我们看看格尺夹住的究竟是什么样的点对。

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)
叉积的符号告诉你：从 P₁→P₂ 到 P₁→P₃ 是往左拐还是往右拐，负值表示右拐，构建凸包时就要弹出拐弯的顶点。
  1. 差分向量 x 分量用 P₂ 减 P₁，得到向量 P₁→P₂ 的横向增量。
    x2−x1,x3−x1x_2-x_1,\quad x_3-x_1
  2. 交叉相乘作差两个差分向量“交叉乘再相减”，这是二维叉积的标准算式。
    (x2−x1)(y3−y1)−(y2−y1)(x3−x1)(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)
  3. 符号判定转向结果为正表示逆时针左转，为负表示顺时针右转，为零表示三点共线。
    cross>0 ⇔ P3 在 P1P2→ 的左侧\text{cross}>0 \ \Leftrightarrow\ P_3 \text{ 在 } \overrightarrow{P_1P_2} \text{ 的左侧}

对踵点对

木匠把格尺架到轮廓上时，一个方向只有一对接触点：上格尺贴着轮廓的“最高点”，下格尺贴着“最低点”。这对被平行支撑线同时碰到的顶点，就是“对踵点对”。名字有点绕，但本质就是“被同一把平行格尺从两侧同时夹住的两个点”。

什么叫支撑线？就是一条恰好碰到多边形、但不会穿进内部的直线。格尺的两片就是一对平行支撑线。沿任意方向 u 投影凸包，投影值最大的顶点在上格尺上，投影值最小的顶点在下格尺上，它们构成该方向的一对对踵点。

最远点对一定是某时刻格尺夹住的那一对：因为若两点距离为 D，则沿连线方向投影，这两点恰好分别是极大和极小值。换句话说，直径的“身影”一定出现在某对的格尺读数里。

对踵点对最多只有 O(n) 对，这就把“所有点对”的汪洋大海缩小成了一条可以沿多边形绕一圈依次检阅的队列。

u⋅Pa=max⁡P∈S (u⋅P),u⋅Pb=min⁡P∈S (u⋅P)\displaystyle u\cdot P_a=\max_{P\in S}\,(u\cdot P),\qquad u\cdot P_b=\min_{P\in S}\,(u\cdot P)
沿方向 u 把凸包所有顶点“投出影子”，影子最远的两个顶点 Pa、Pb 就是一对对踵点，此时平行支撑线恰好同时经过它们。
  1. 方向向量 u格尺的朝向，可以想象成手电筒的光线方向。
    u=(ux,uy),∣u∣=1u=(u_x,u_y),\quad |u|=1
  2. 点积投影每个顶点在 u 方向上的“影子长度”，点积运算即投影。
    u⋅P=ux x+uy yu\cdot P=u_x\,x+u_y\,y
  3. 取极大极小影子最长的顶点 Pa 与最短的顶点 Pb 恰好被两片平行格尺夹住。
    max⁡P∈S(u⋅P),min⁡P∈S(u⋅P)\max_{P\in S}(u\cdot P),\quad \min_{P\in S}(u\cdot P)

核心思想

木匠不会每转一个角度都把格尺重新架一遍——他让格尺贴住一条边，找到对面的“最高点”，然后顺时针微转，让格尺滑到下一条边，对面的“最高点”只会继续前进，绝不会倒退。这个“只进不退”的岗哨，就是旋转卡壳的心脏。

具体做法：从凸包的某条边 E₁ 开始，沿逆时针顺序遍历每条边。对当前边 (i, i+1)，用“面积法”找到离它最远的顶点 j；当边转到 (i+1, i+2) 时，对踵点 j 从当前位置继续向前试探即可。为什么能这样？因为顶点到固定边的距离函数在凸包上是单峰的——先增后减，不可能出现多个起伏。

面积法判定依靠三角形面积：点 j 到边 (i, i+1) 的距离正比于三角形 (Pᵢ, Pᵢ₊₁, Pⱼ) 的面积，而面积恰好是叉积绝对值的一半。只要下一个顶点的面积更大，就让 j 前进。

这个“只进不退”的规则，让整圈旋转中指针移动的总距离不超过一圈，是 O(n) 奇迹的来源。木匠的格尺从第一条边滑到最后一条边，岗哨总共只绕了不到两圈。

area(Pi,Pi+1,Pj)<area(Pi,Pi+1,Pj+1) ⟹ j←j+1\displaystyle \text{area}(P_i,P_{i+1},P_j)<\text{area}(P_i,P_{i+1},P_{j+1})\ \Longrightarrow\ j\leftarrow j+1
这是一个“谁更远谁上岗”的规则：下一个顶点离当前边更远，格尺夹住的点就换到它。
  1. 当前距离点 j 到边 (i, i+1) 的距离用三角形面积衡量。
    area(Pi,Pi+1,Pj)=12∣cross(Pi,Pi+1,Pj)∣\text{area}(P_i,P_{i+1},P_j)=\tfrac12\bigl|\text{cross}(P_i,P_{i+1},P_j)\bigr|
  2. 试探下一位比较顶点 j 与 j+1 谁离当前边更远。
    area(Pi,Pi+1,Pj+1)>area(Pi,Pi+1,Pj)\text{area}(P_i,P_{i+1},P_{j+1})>\text{area}(P_i,P_{i+1},P_j)
  3. 推进指针只要下一位更远，j 就前进一位，重复直到面积开始下降。
    j=(j+1) mod nj=(j+1)\bmod n

最远点对

木匠转完一整圈格尺后，把所有读数放在一起比大小——最大读数对应的那对接触点，就是最远点对，距离称为凸多边形直径。因为我们已经知道候选只可能是对踵点对，所以无需计算全部 n²/2 个距离。

算法像流水线一样执行：对每个顶点 i，找到它的对踵点 antip[i]，计算两者距离平方，更新全局最大值。由于 j 随 i 单调推进，整个流水线一个方向走完，每条边平均只需要 O(1) 次距离计算。

距离比较用平方而非开方，因为开方是单调函数，不影响“谁更大”的判断，还能省去浮点开根的成本。这是工程实现中典型的“省算力”小技巧。

格尺转完一圈，木匠在纸上记下最大读数对应的两个钉子——直径到手，全程没有回头路。

D=max⁡0≤i<n ∣Pi Pantip[i]∣2=max⁡0≤i<n ((xi−xai)2+(yi−yai)2)\displaystyle D=\max_{0\le i<n}\ \bigl|P_i\,P_{\text{antip}[i]}\bigr|^2=\max_{0\le i<n}\ \Bigl((x_i-x_{a_i})^2+(y_i-y_{a_i})^2\Bigr)
直径 = 所有“顶点与其对踵点”距离平方的最大值，aᵢ 即顶点 i 的对踵点下标。
  1. 取定顶点遍历凸包每个顶点 i，aᵢ 是它此刻的对踵点。
    i=0,1,…,n−1i=0,1,\dots,n-1
  2. 距离平方两点横纵坐标差分别平方再相加，避免开方。
    (xi−xai)2+(yi−yai)2(x_i-x_{a_i})^2+(y_i-y_{a_i})^2
  3. 全局最值在一圈遍历中不断比较并保留最大者。
    D=max⁡{⋯ }D=\max\{\cdots\}

最小矩形

木匠还有一桩活：给这块木块找到能通过的最窄“门框”，也就是最小宽度矩形。他惊喜地发现，最优矩形的四条边里，至少有一条与凸包的某条边重合——换句话说，矩形是“贴着”某条边立起来的，不会悬空乱转。

数学上，对每条边 E=(Pᵢ, Pᵢ₊₁)，矩形的方向由 E 决定，矩形的高等于离 E 最远的对踵点到 E 的垂直距离。这个距离恰好等于“三角形面积 × 2 ÷ 底边长”，也就是叉积绝对值除以边长。逐边求出高度，最小的高度就是最小宽度矩形的高。

矩形的最小宽度确定后，另外两条支撑线分别穿过“最左点”和“最右点”，于是这个矩形由一条边加三个极点共同确定。值得注意的是，最小宽度矩形未必是面积最小的外接矩形，工程中按需二选一。

木匠挨个试过每条边对应的门框方向，挑出最窄的一扇——这个方向就是木块搬运时的最佳姿态。

hi=∣cross(Pi,Pi+1,Pj)∣∣PiPi+1∣,wmin⁡=min⁡0≤i<nhi\displaystyle h_i=\frac{\bigl|\text{cross}(P_i,P_{i+1},P_j)\bigr|}{\bigl|P_iP_{i+1}\bigr|},\qquad w_{\min}=\min_{0\le i<n} h_i
每条边对应一个“门框高度”，高度 = 叉积绝对值 ÷ 底边长度；所有边中最小的 hᵢ 就是最小宽度矩形的高。
  1. 分子是平行四边形面积叉积绝对值等于底边与高围成的平行四边形面积。
    ∣cross(Pi,Pi+1,Pj)∣=底边×hi\bigl|\text{cross}(P_i,P_{i+1},P_j)\bigr|=\text{底边}\times h_i
  2. 除以底边得高平行四边形面积除以底边长度，就是点到边的垂直距离。
    ∣PiPi+1∣=(xi+1−xi)2+(yi+1−yi)2\bigl|P_iP_{i+1}\bigr|=\sqrt{(x_{i+1}-x_i)^2+(y_{i+1}-y_i)^2}
  3. 取最小值所有边的“门框高度”中最小的那个，即最小宽度。
    wmin⁡=min⁡ihiw_{\min}=\min_i h_i

复杂度分析

也许你会惊讶：格尺转一圈就能搞定，凭什么是 O(n) 而不是 O(n²)？关键在于“指针只进不退”的平摊性质。指针 j 虽然在局部会前进很多步，但从全局看，总共推进的次数不超过凸包顶点数 n。

每次“边”切换时，j 从上次位置继续，可能再前进若干步。把所有前进步数加起来，由于 j 沿顶点环单调绕行且最多绕一圈，总和不超过 n。因此整个旋转阶段的总步数是“每条边一次固定操作 + 所有前进步数”= O(n) + O(n) = O(n)。

对比暴力法 O(n²) 的两两距离计算，旋转卡壳在凸包顶点数达到上万时依然轻快。不过要注意，若输入是散点，求凸包本身的排序阶段是 O(n log n)，这通常是整个流程的主要开销。

木匠的秘诀从来不是“转得快”，而是“不重走回头路”。这把格尺之所以高效，正因为它深刻地利用了凸多边形的单峰性质。

\displaystyle \sum_{i=0}^{n-1}\Delta j_i\ \le\ n\quad\Longrightarrow\quadT_{\text{rot}}(n)=O(n)
Δjᵢ 是处理第 i 条边时指针前进的步数；所有步数总和不超过 n，所以旋转卡壳是线性时间。
  1. 定义前进量Δjᵢ 表示第 i 轮中指针 j 向前移动的次数。
    Δji≥0\Delta j_i\ge 0
  2. 总和有界指针绕环一圈总前进量至多 n。
    ∑i=0n−1Δji≤n\sum_{i=0}^{n-1}\Delta j_i\le n
  3. 得出线性每轮固定工作 O(1)，故总时间 O(n)。
    Trot(n)=O(n)T_{\text{rot}}(n)=O(n)

应用场景

这套“平行格尺”的思想在工程界遍地开花。想象两个游戏角色各自被一个凸多边形包围盒包裹，要判断它们是否碰撞，只需检查沿某个方向投影是否重叠——如果存在一个方向让两段“影子”分离，就不碰撞。旋转卡壳可以快速枚举所有候选方向，比逐边尝试更聪明。

分离轴判定的核心是：若存在方向 u，使物体 A 的投影最大值小于物体 B 的投影最小值，则两者无碰撞。这个判定在物理引擎中配合旋转卡壳预先计算好的支撑点，能把碰撞检测从逐点判断降为几次点积运算。

木匠的格尺从木板车间走进了游戏引擎、机器人传感器和编译器优化——任何时候你需要知道“谁离得最远”或“哪个方向最窄”，旋转卡壳都能用一圈优雅的旋转给出答案。

∃ u:max⁡P∈A(P⋅u)<min⁡Q∈B(Q⋅u) ⟺ A∩B=∅\displaystyle \exists\, u:\quad \max_{P\in A}(P\cdot u)<\min_{Q\in B}(Q\cdot u)\ \Longleftrightarrow\ A\cap B=\varnothing
存在一个方向让两物体的影子错开，则它们不相交；旋转卡壳负责快速找到这样的方向。
  1. 沿 u 投影把两个凸多边形的所有顶点投影到方向 u 上。
    P⋅u,Q⋅uP\cdot u,\quad Q\cdot u
  2. 区间分离A 的最大投影小于 B 的最小投影，说明影子有缝隙。
    max⁡P∈A(P⋅u)<min⁡Q∈B(Q⋅u)\max_{P\in A}(P\cdot u)<\min_{Q\in B}(Q\cdot u)
  3. 等价判据只要存在一个分离方向，两凸多边形必不相交。
    ∃u: 分离  ⟺  A∩B=∅\exists u:\ \text{分离} \iff A\cap B=\varnothing

AI 应用场景

自动驾驶与机器人的碰撞检测

阶段：感知与决策中的几何校验

解决的问题：传统方法把每个障碍物当点云两两比较，O(n²) 代价在高速行驶时根本无法实时；用凸包+旋转卡壳先把障碍物压缩成凸多边形，再沿分离轴快速判定碰撞，单次检测降到几十次点积。

具体案例：无人车用激光雷达扫描前方，把车辆、行人目标聚类后生成凸包，旋转卡壳实时计算最远点对来估计目标尺度，并用分离轴判定本车包围盒与目标是否相交，为刹车决策留出毫秒级余量。

游戏引擎的包围盒优化

阶段：物理模拟与场景管理

解决的问题：游戏中成千上万的模型若直接做多边形碰撞检测会拖垮帧率；先用旋转卡壳求出每个模型的最小宽度矩形作为粗碰撞包围盒，宽相位剔除后再进入精检测，大幅降低计算量。

具体案例：在某动作游戏中，角色的攻击判定区域被建模为凸多边形，引擎每帧用旋转卡壳计算其最小外接矩形与场景障碍物的分离轴，快速排除 90% 不必要的碰撞计算，稳定 60 帧运行。

旋转目标检测的后处理

阶段：目标检测模型输出后处理

解决的问题：检测模型输出的旋转框往往带噪声，需要把框“贴合”真实物体的最小外接矩形；求取物体分割掩膜的凸包后，用旋转卡壳枚举各边方向，找到面积或宽度最小的外接矩形，得到更精准的检测框。

具体案例：在遥感影像船舶检测中，模型输出语义分割掩膜，后端用旋转卡壳求最小外接矩形得到船舶朝向和尺寸，用于航迹预测与港口调度，精度比固定轴对齐框提升约 15%。

Python 演示

python76 行
import math  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(points):    points = sorted(points)    lower = []    for p in points:        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:            lower.pop()        lower.append(p)    upper = []    for p in reversed(points):        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:            upper.pop()        upper.append(p)    return lower[:-1] + upper[:-1]  def dist2(a, b):    return (a[0]-b[0])**2 + (a[1]-b[1])**2  def rotating_calipers_diameter(hull):    n = len(hull)    j = 1    best_d2 = 0    best_pair = (0, 0)    for i in range(n):        nxt = (i + 1) % n        while True:            nxtj = (j + 1) % n            if abs(cross(hull[i], hull[nxt], hull[nxtj])) > abs(cross(hull[i], hull[nxt], hull[j])):                j = nxtj            else:                break        d = dist2(hull[i], hull[j])        if d > best_d2:            best_d2 = d            best_pair = (i, j)    return math.sqrt(best_d2), best_pair  def minimum_width(hull):    n = len(hull)    j = 1    min_w = float("inf")    best_edge = (0, 1)    for i in range(n):        nxt = (i + 1) % n        while True:            nxtj = (j + 1) % n            if abs(cross(hull[i], hull[nxt], hull[nxtj])) > abs(cross(hull[i], hull[nxt], hull[j])):                j = nxtj            else:                break        base = math.hypot(hull[nxt][0]-hull[i][0], hull[nxt][1]-hull[i][1])        h = abs(cross(hull[i], hull[nxt], hull[j])) / base        if h < min_w:            min_w = h            best_edge = (i, nxt)    return min_w, best_edge  if __name__ == "__main__":    points = [(0, 0), (1, 5), (4, 7), (7, 4), (6, 0), (3, 3), (2, 4), (5, 1)]    hull = convex_hull(points)    print("凸包:", hull)    diameter, (a, b) = rotating_calipers_diameter(hull)    print("最远点对:", hull[a], hull[b])    print("直径:", round(diameter, 4))    width, _ = minimum_width(hull)    print("最小宽度:", round(width, 4))
目的：从散点构建凸包，再用旋转卡壳的“面积法”在同一轮遍历中求出最远点对（直径）和最小宽度矩形的高度。
  1. while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:叉积非正说明要右拐或共线，弹出该点，保证凸包逆时针有序。
  2. return lower[:-1] + upper[:-1]上下链去掉首尾重复点后拼成完整凸包。
  3. while True:内层循环用面积法推进对踵点指针，直到下一个点不再更远。
  4. if abs(cross(hull[i], hull[nxt], hull[nxtj])) > abs(cross(hull[i], hull[nxt], hull[j])):面积更大即离边更远，对踵点前进。
  5. j = nxtj指针 j 只前进不后退，这是 O(n) 的来源。
  6. d = dist2(hull[i], hull[j])用距离平方比较避免开方，性能更好。
  7. base = math.hypot(...)计算底边长度，用于把面积换算成高度。

常见误区

误区最远点对不就是把所有点都两两算一遍距离，取最大的那个吗？反正点也不多，O(n²) 也无所谓。

正解当点的规模从几千涨到十万，O(n²) 会从毫秒级涨到小时级。旋转卡壳通过“对踵点”这条数学捷径，把候选从 n² 压缩到 O(n)，因为最远点对只可能出现在被平行格尺同时夹住的点对中。橡皮筋已经帮我们圈掉了所有内部点，格尺再帮我们滤掉了大多数外部点对。

为何常见：人脑直觉上“最远”就是要全部量一遍，忽略了凸多边形结构带来的单调性红利。

误区给一堆乱点，直接跑旋转卡壳就能求出最远点对，不需要先做凸包。

正解旋转卡壳是围绕凸多边形转圈、利用顶点有序性设计的，散点没有“一圈”的概念。正确流程是先求凸包，把散点压缩成有序凸多边形，再上旋转卡壳。少了凸包这一步，等于没把橡皮筋套上就急着拿格尺乱夹。

为何常见：教程中常把“给定凸包”作为前提一笔带过，初学者容易漏掉前置步骤。

误区判断对踵点时要计算真正的三角形面积，或者比较两条边的夹角，不然会不准确。

正解面积法只需要叉积的绝对值即可——它和真实面积只差一个常数 1/2，比较大小完全不受影响。用角度或斜率判断反而会引入昂贵的反三角函数，还容易因接近 90° 时精度抖动而出错。格尺的决定不需要精确读数，只需要“哪个更高”。

为何常见：学校教的叉积常常伴着一堆几何意义，让人误以为必须“算到底”。

误区宽度最小和面积最小是一回事，求到最小宽度矩形就完成了。

正解两者目标函数不同。宽度最小矩形优化的是“最短边”，面积最小矩形优化的是“长×宽”。对同一个凸多边形，这两个矩形的方向和大小都可能不同。工程中要根据需求二选一——门框看宽度，包装盒看面积。

为何常见：日常说“最小的盒子”时语义含糊，未区分面积与宽度的优化目标。

面试题

Q1. 旋转卡壳算法主要用于解决哪类问题？

单选题 · easy

  • A.字符串匹配
  • B.凸多边形上的极值问题（最远点对、最小宽度等）← 正确答案
  • C.图的单源最短路
  • D.数组排序

答案：B。旋转卡壳是围绕凸多边形的对踵点做线性扫描的算法，典型应用是求最远点对、直径与最小宽度矩形；字符串、图、排序各有专属算法。

Q2. 对给定凸包，旋转卡壳求最远点对的时间复杂度是？

单选题 · easy

  • A.O(n)← 正确答案
  • B.O(n log n)
  • C.O(n²)
  • D.O(n³)

答案：A。指针 j 只前进不后退，总前进步数不超过 n，每条边固定工作 O(1)，所以是 O(n)。O(n log n) 是散点求凸包的排序代价，不是旋转卡壳本身的复杂度。

Q3. 最远点对的两个端点一定是凸多边形的？

单选题 · easy

  • A.任意相邻顶点
  • B.一对话踵点← 正确答案
  • C.随机两个顶点
  • D.重心两侧的点

答案：B。沿最远点对连线方向投影，两端点恰好是投影最大与最小点，因此必然存在一对平行支撑线同时经过它们，即对踵点对。

Q4. 判断对踵点是否应继续前进时，常比较的量是？

单选题 · mid

  • A.两条边的长度之比
  • B.三角形面积的叉积绝对值← 正确答案
  • C.两点之间的距离之和
  • D.多边形周长

答案：B。点到边的距离正比于叉积绝对值，比较叉积就能判断哪个顶点离当前边更远，无需真正计算角度或距离。

Q5. 为什么对踵点指针可以单调推进而不回退？

单选题 · mid

  • A.因为凸包上的距离函数是单峰的← 正确答案
  • B.因为顶点已按字典序排序
  • C.因为随机化分治保证
  • D.因为用了动态规划

答案：A。凸多边形顶点到固定边的距离随顶点顺序先增后减，呈单峰，因此从当前位置继续试探即可，不必回退扫描，这正是 O(n) 的关键。

Q6. 最小宽度矩形的高 h 等于？

单选题 · mid

  • A.最长边长度
  • B.叉积绝对值除以底边长度← 正确答案
  • C.底边长度除以叉积绝对值
  • D.多边形直径

答案：B。叉积绝对值等于“底边 × 高”的平行四边形面积，除以底边长就得到对踵点到边的垂直距离，即矩形的高。

Q7. 旋转卡壳求直径时，实际需要比较的候选点对数量级是？

单选题 · hard

  • A.O(n)← 正确答案
  • B.O(n log n)
  • C.O(n²)
  • D.O(1)

答案：A。候选只有顶点与对踵点组成的对踵点对，对踵点对总数是 O(n)，因此直径只需在线性对数量中比较。

Q8. 下列哪些问题可以用旋转卡壳求解？

多选题 · mid

  • A.凸多边形直径← 正确答案
  • B.最远点对← 正确答案
  • C.最小宽度外接矩形← 正确答案
  • D.最近点对

答案：ABC。旋转卡壳围绕对踵点可求直径、最远点对、最小宽度与最小外接矩形；最近点对通常在点集内部，不属于对踵点范畴，常用分治法解决。

Q9. 求散点凸包的常见算法包括？

多选题 · mid

  • A.Graham 扫描← 正确答案
  • B.Andrew 单调链← 正确答案
  • C.冒泡排序
  • D.旋转卡壳

答案：AB。Graham 扫描和 Andrew 单调链都是基于极角/坐标排序后维护凸链的经典算法；冒泡排序是排序算法，旋转卡壳是在凸包建好后使用的后处理算法。

Q10. 关于对踵点对，下列说法正确的是？

多选题 · hard

  • A.每条凸包边对应一个离它最远的对踵点← 正确答案
  • B.对踵点对被一对平行支撑线同时接触← 正确答案
  • C.对踵点对总数是 O(n)← 正确答案
  • D.对踵点对之间的距离一定相等

答案：ABC。每条边经面积法可找到最远对踵点，支撑线平行是对踵点的定义，总对数是线性量级；距离显然各不相同，D 错误。