旋转卡壳（凸包直径）
计算几何 · 最远点对 · O(n)
最远的两个点在哪
给一堆点，找相距最远的两个（点集的直径）。暴力枚举所有点对是 O(n²)。第一个观察：最远点对的两端一定都在凸包上——内部点到谁都不会比凸包顶点更远。但只在凸包顶点上枚举仍是 O(m²)。旋转卡壳（Rotating Calipers）把它压到 O(n)。
对踵点只会单调前移
想象拿两块平行卡板夹住凸包，然后让它们贴着凸包旋转一整圈。任一时刻两块板各贴着凸包的一条边或一个顶点——离一条边最远的那个顶点叫这条边的对踵点。关键性质：边沿凸包逆时针推进时，对踵点也只会朝同方向单调前移，绝不回头。于是用三角形面积比较（底边固定时面积越大点越远）：只要「下一个顶点」离当前边更远，对踵点就前移一格。每条边稳定后，检查边两端点 ↔ 对踵点两个候选距离即可。整圈下来边走 n 步、对踵点也最多走 n 步，O(n)。
下面沿用凸包页的 7 个点（凸包 6 顶点，常显为绿多边形）。点「下一步」逐步看：琥珀粗线是当前推进到的凸包边、蓝色虚线是本步「边端点↔对踵点」的候选连线、绿色粗线是到目前为止的最远点对。转完一圈，直径 = 6（点对 (0,3)↔(6,3)），与暴力枚举一致。右侧代码随每一步同步高亮。
在凸包上找最远点对（直径）：像两块平行卡板夹住凸包旋转——对每条边，离它最远的「对踵点」只会单调前移
1function diameter(hull: Pt[]): number {
2 const m = hull.length;
3 const area2 = (a: Pt, b: Pt, c: Pt) => Math.abs(cross(a, b, c));
4 let j = 1, best = 0;
5 for (let i = 0; i < m; i++) { // 逐条凸包边推进
6 const ni = (i + 1) % m;
7 while (area2(hull[i], hull[ni], hull[(j + 1) % m]) >
8 area2(hull[i], hull[ni], hull[j])) {
9 j = (j + 1) % m; // 对踵点单调前移（面积更大 → 更远）
10 }
11 best = Math.max(best, d2(hull[i], hull[j]), d2(hull[ni], hull[j])); // 两候选
12 }
13 return best; // 直径²（一圈转完）
14}
凸包顶点6
当前最远²-
1 / 8
一圈搞定的对偶技巧
直径在凸包上：最远点对两端必为凸包顶点。
对踵点：离一条边最远的顶点；面积比较（叉积绝对值）判断远近。
单调性：边推进时对踵点只前移不回头 → 两指针各走一圈，O(n)。
候选：每条边只需检查「边两端 ↔ 对踵点」两个距离。
对踵点：离一条边最远的顶点；面积比较（叉积绝对值）判断远近。
单调性：边推进时对踵点只前移不回头 → 两指针各走一圈，O(n)。
候选：每条边只需检查「边两端 ↔ 对踵点」两个距离。
同一套「卡板旋转」还能求最小外接矩形（面积最小的包围矩形一定有一条边贴着凸包的边）、凸包宽度（最窄方向）、两凸包间最近/最远距离——旋转卡壳是凸包之上最锋利的一把刀。