旋转卡壳解法：POJ-2187 Beauty Contest 最远距离详解

一、问题背景与数学本质

POJ-2187 Beauty Contest（最美牛评选）是一道经典的计算几何问题，其核心目标是在二维平面的点集中找到两点间的最大欧氏距离。该问题可抽象为凸包（Convex Hull）上的最远点对问题——当点集构成凸多边形时，最远点对必然位于凸包的顶点集合中。这一结论将问题规模从O(n²)的暴力枚举降至O(n log n)的凸包构建加上O(n)的最远点对搜索，成为旋转卡壳算法的典型应用场景。

数学上，两点P(x₁,y₁)与Q(x₂,y₂)的欧氏距离公式为：
[ d(P,Q) = \sqrt{(x₂-x₁)^2 + (y₂-y₁)^2} ]
直接计算所有点对的距离需进行C(n,2)=n(n-1)/2次运算，当n=50000时，计算量高达1.25×10⁹次，显然不可行。而旋转卡壳通过几何不变量与方向性搜索，将复杂度降至线性级别。

二、旋转卡壳算法原理

1. 凸包构建：Andrew算法

旋转卡壳的前提是获取点集的凸包。Andrew算法通过排序与单调链构建凸包，步骤如下：

1. 将点集按x坐标升序排序（x相同则按y升序）
2. 构建下凸包：从左至右扫描，维护一个栈结构，当新点与栈顶两点构成的转向非逆时针时弹出栈顶
3. 构建上凸包：从右至左扫描，同理维护栈结构
4. 合并上下凸包，去除重复的起点

该算法时间复杂度为O(n log n)（排序阶段），空间复杂度O(n)。

2. 旋转卡壳核心思想

旋转卡壳通过维护一对平行线（卡壳）夹住凸包，并旋转这对线360度，在旋转过程中动态计算卡壳边对应的“最远点”。具体步骤：

1. 初始化：选择凸包上一条边作为起始边
2. 对每条边，找到凸包上距离该边最远的顶点（通过叉积判断）
3. 计算该顶点与边两端点的距离，更新全局最大值
4. 旋转卡壳至下一条边，重复步骤2-3

关键几何性质：凸包上距离某边最远的顶点必然在该边对应的反方向延长线上。这一性质保证了算法的正确性。

三、POJ-2187实现关键点

1. 输入处理与凸包构建

struct Point {
    double x, y;
    bool operator < (const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
};
vector<Point> convexHull(vector<Point>& P) {
    int n = P.size(), k = 0;
    if (n <= 1) return P;
    sort(P.begin(), P.end());
    vector<Point> H(2*n);
    // 下凸包
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }
    // 上凸包
    for (int i = n-2, t = k+1; i >= 0; --i) {
        while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }
    H.resize(k-1);
    return H;
}

其中cross(O,A,B)计算向量OA与OB的叉积，判断转向方向。

2. 旋转卡壳实现

double rotatingCalipers(vector<Point>& hull) {
    int n = hull.size();
    if (n == 2) return dist(hull[0], hull[1]);
    double max_dist = 0;
    int j = 1;
    for (int i = 0; i < n; ++i) {
        Point a = hull[i], b = hull[(i+1)%n];
        // 找到距离边ab最远的点
        while (abs(cross(a, b, hull[j])) <= abs(cross(a, b, hull[(j+1)%n]))) {
            j = (j+1)%n;
        }
        // 更新最大距离
        max_dist = max(max_dist, dist(a, hull[j]));
        max_dist = max(max_dist, dist(b, hull[j]));
    }
    return max_dist;
}

该函数遍历每条凸包边，通过叉积比较动态更新最远点j，并计算距离。

四、性能优化与边界处理

1. 精度控制

浮点数比较需设置容差，例如：

const double EPS = 1e-8;
bool eq(double a, double b) { return abs(a-b) < EPS; }

在叉积比较时使用eq(cross(...), 0)判断共线性。

2. 特殊情况处理

• 点集共线：此时凸包退化为线段，直接返回两端点距离
• 重复点：预处理阶段去重
• 小规模点集（n≤3）：直接计算所有点对距离

五、算法复杂度分析

• 凸包构建：O(n log n)（排序） + O(n)（单调链）
• 旋转卡壳：O(n)（每条边处理O(1)时间）
  总复杂度O(n log n)，优于暴力法的O(n²)。当n=50000时，旋转卡壳约需1.5×10⁶次运算，而暴力法需1.25×10⁹次。

六、实际应用与扩展

旋转卡壳不仅可用于最远点对，还可解决：

• 最小面积/周长矩形包围盒
• 凸包直径（与最远点对等价）
• 凸多边形交集面积

在计算机图形学、机器人路径规划、图像处理等领域有广泛应用。例如，在碰撞检测中，快速计算两个凸多边形间的最大距离可优化物理引擎性能。

七、POJ-2187解题建议

1. 输入预处理：去重、检查点数是否≥2
2. 凸包验证：输出凸包顶点数，确认构建正确
3. 调试技巧：绘制凸包与最远点对，可视化验证
4. 精度测试：构造共线、对称等特殊用例

八、总结

旋转卡壳通过几何变换将二维最远点对问题转化为线性扫描问题，其核心在于利用凸包的几何性质减少计算量。POJ-2187作为经典例题，要求开发者掌握凸包构建与旋转卡壳的协同应用，理解叉积在方向判断中的作用，以及浮点数精度处理技巧。掌握该算法后，可进一步探索其在三维空间中的扩展（如使用球面旋转卡壳），或结合分治思想处理超大规模点集。