C++旋转卡壳算法怎么求平面点集最远点对-C++-PHP中文网

旋转卡壳能求最远点对，因凸包上最远点对必为顶点间的对踵点对，其通过双指针维护平行支撑线，在o(n)内遍历所有对踵点对；主循环固定i、推进j使叉积递增，j继承上轮位置，用平方距离比较，凸包须逆时针无重复存储。

c++旋转卡壳算法怎么求平面点集最远点对

旋转卡壳为什么能求最远点对

因为凸包上最远点对一定出现在凸包顶点之间，而旋转卡壳通过维护一对平行支撑线，在 O(n) 时间内遍历所有可能的对踵点对（antipodal pairs），跳过明显不可能更远的组合。暴力枚举所有点对是 O(n²)，而先求凸包再旋转卡壳整体是 O(n log n)（主要开销在凸包构造）。

怎么写一个可靠的旋转卡壳主循环

核心是用双指针模拟两条平行切线绕凸包逆时针旋转：固定一个点 i，让另一个点 j 沿凸包移动，使得三角形 convex[i], convex[i+1], convex[j] 的有向面积（即叉积）持续增大——这说明 j 还没到达当前 i 的对踵点。一旦面积开始减小，就停止推进 j，记录距离并推进 i。

实操建议：

凸包必须按逆时针顺序存储，且首尾不重复（如 Graham 扫描后去掉最后一个重复点）
j 从 0 开始，每次内层循环用 (j + 1) % m 取模，避免越界
距离比较用平方距离（dx*dx + dy*dy），避免开方误差和性能损耗
不要在每次 i 变化时把 j 归零——要继承上一轮位置，这是 O(n) 的关键

常见错误：凸包退化或点数太少怎么办

当输入点数 ≤ 1 时直接返回 0；≤ 2 时直接返回两点距离；三点共线时凸包可能只剩两个点（线段），此时最远点对就是端点，旋转卡壳循环仍可运行（m == 2 时 j 只会在两个索引间切换），但需确保凸包函数能正确处理共线点——推荐在 Graham 或 Andrew 算法中保留所有共线边界点，或至少保留首尾极值点。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

容易踩的坑：

cross(o, a, b) == 0 判共线时，若用整数坐标要防溢出；浮点要用 abs(cross)
凸包点数 m == 1 时，旋转卡壳循环不会执行，必须单独处理
使用 std::vector 存凸包，别用 array 写死大小，点集规模不确定

一个最小可验证的 C++ 片段

以下为旋转卡壳主干逻辑（假设 convex 是逆时针凸包，至少 2 个点）：

int m = convex.size();
if (m == 1) return 0;
if (m == 2) return dist2(convex[0], convex[1]);
int j = 1;
long long maxd2 = 0;
for (int i = 0; i 
<p>注意：<code>cross(a, b, c)</code> 计算的是 <code>(b-a) × (c-a)</code>，符号决定 <code>c</code> 在直线 <code>ab</code> 左/右侧；这里用它比较“高度”来决定是否继续转 <code>j</code>。实际使用时务必校验叉积方向与凸包朝向一致。</p>
<p>最易被忽略的是：凸包构造函数是否稳定、是否去重、是否处理了所有边界情况——很多“旋转卡壳返回错误结果”的问题，根源其实在前一步的凸包没做对。</p>

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！