旋转卡壳（凸包直径）

计算几何 · 最远点对 · O(n)

最远的两个点在哪

给一堆点，找相距最远的两个（点集的直径）。暴力枚举所有点对是 O(n²)。第一个观察：最远点对的两端一定都在凸包上——内部点到谁都不会比凸包顶点更远。但只在凸包顶点上枚举仍是 O(m²)。旋转卡壳（Rotating Calipers）把它压到 O(n)。

对踵点只会单调前移

想象拿两块平行卡板夹住凸包，然后让它们贴着凸包旋转一整圈。任一时刻两块板各贴着凸包的一条边或一个顶点——离一条边最远的那个顶点叫这条边的对踵点。关键性质：边沿凸包逆时针推进时，对踵点也只会朝同方向单调前移，绝不回头。于是用三角形面积比较（底边固定时面积越大点越远）：只要「下一个顶点」离当前边更远，对踵点就前移一格。每条边稳定后，检查边两端点 ↔ 对踵点两个候选距离即可。整圈下来边走 n 步、对踵点也最多走 n 步，O(n)。

下面沿用凸包页的 7 个点（凸包 6 顶点，常显为绿多边形）。点「下一步」逐步看：琥珀粗线是当前推进到的凸包边、蓝色虚线是本步「边端点↔对踵点」的候选连线、绿色粗线是到目前为止的最远点对。转完一圈，直径 = 6（点对 (0,3)↔(6,3)），与暴力枚举一致。右侧代码随每一步同步高亮。

在凸包上找最远点对（直径）：像两块平行卡板夹住凸包旋转——对每条边，离它最远的「对踵点」只会单调前移

一圈搞定的对偶技巧

直径在凸包上：最远点对两端必为凸包顶点。
对踵点：离一条边最远的顶点；面积比较（叉积绝对值）判断远近。
单调性：边推进时对踵点只前移不回头 → 两指针各走一圈，O(n)。
候选：每条边只需检查「边两端 ↔ 对踵点」两个距离。

同一套「卡板旋转」还能求最小外接矩形（面积最小的包围矩形一定有一条边贴着凸包的边）、凸包宽度（最窄方向）、两凸包间最近/最远距离——旋转卡壳是凸包之上最锋利的一把刀。