旋转卡壳能求最远点对，因凸包上最远点对必为顶点间的对踵点对，其通过双指针维护平行支撑线，在O(n)内遍历所有对踵点对；主循环固定i、推进j使叉积递增，j继承上轮位置，用平方距离比较，凸包须逆时针无重复存储。
旋转卡壳为什么能求最远点对
因为凸包上最远点对一定出现在凸包顶点之间，而旋转卡壳通过维护一对平行支撑线，在 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++免费学习笔记（深入）”；
组合式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 < m; i++) {
int nxt = (i + 1) % m;
while (cross(convex[i], convex[nxt], convex[j]) < cross(convex[i], convex[nxt], convex[(j + 1) % m]))
j = (j + 1) % m;
maxd2 = max(maxd2, dist2(convex[i], convex[j]));
}
注意：cross(a, b, c) 计算的是 (b-a) × (c-a)，符号决定 c 在直线 ab 左/右侧；这里用它比较“高度”来决定是否继续转 j。实际使用时务必校验叉积方向与凸包朝向一致。
最易被忽略的是：凸包构造函数是否稳定、是否去重、是否处理了所有边界情况——很多“旋转卡壳返回错误结果”的问题，根源其实在前一步的凸包没做对。
