POJ-2187：Beauty Contest（最简单的旋转卡壳，求最远距离）

引言

在计算几何领域，”最远点对”问题是一个经典且重要的课题。给定平面上的N个点，如何高效地找到其中距离最远的两个点？对于小规模数据，暴力枚举所有点对即可；但对于大规模数据（如N>10^5），O(N^2)的暴力算法显然不可行。POJ-2187 Beauty Contest问题正是这一问题的典型实例，而旋转卡壳（Rotating Calipers）算法则以其O(N)的线性时间复杂度成为最优解。本文将深入探讨如何用最简单的旋转卡壳实现求解最远距离，为开发者提供从理论到实践的完整指南。

问题定义

POJ-2187 Beauty Contest问题的核心是：给定平面上的N个点（3≤N≤50,000），找出其中距离最远的两个点，并输出其距离的平方（避免浮点数精度问题）。输入为点的坐标，输出为一个整数（距离的平方）。例如，对于三个点(0,0)、(3,0)、(0,4)，最远点对是(0,0)与(0,4)或(3,0)与(0,4)，距离平方为25。

旋转卡壳算法原理

旋转卡壳是一种通过动态维护”卡壳”（两条平行直线）来遍历凸包上点对的算法。其核心思想是：最远点对一定出现在凸包的顶点上。因此，算法步骤如下：

1. 计算凸包：使用Andrew算法或Graham扫描法，将点集转化为凸多边形（凸包）。
2. 旋转卡壳遍历：固定一条边，旋转另一条边寻找最远点对。
3. 更新最远距离：在旋转过程中，动态计算当前边对的距离，并更新最大值。

为什么凸包是关键？

凸包的性质保证了任意两点连线都在凸包内部或边上。若最远点对不在凸包上，则至少存在一个点在凸包外，可通过调整点对使其更远，矛盾。因此，只需在凸包顶点中寻找最远点对。

算法实现步骤

步骤1：计算凸包

以Andrew算法为例：

1. 将点按x坐标排序（x相同按y排序）。
2. 初始化空栈，依次将点压入栈，同时维护下凸包（逆时针方向）。
3. 反向遍历点集，维护上凸包（顺时针方向）。
4. 合并上下凸包，去除重复点。

vector<Point> convexHull(vector<Point>& points) {
    sort(points.begin(), points.end());
    vector<Point> hull;
    for (int i = 0; i < 2; i++) {
        int start = hull.size();
        for (auto& p : points) {
            while (hull.size() >= start + 2 && 
                   cross(hull[hull.size()-2], hull.back(), p) <= 0)
                hull.pop_back();
            hull.push_back(p);
        }
        hull.pop_back(); // 去除重复起点
        reverse(points.begin(), points.end());
    }
    return hull;
}

步骤2：旋转卡壳求最远点对

1. 初始化最远距离max_dist = 0。
2. 对于凸包的每条边(hull[i], hull[i+1])，固定该边为基准边。
3. 旋转另一条边（初始为垂直方向），寻找与基准边最远的点hull[j]。
4. 计算dist_sq(hull[i], hull[j])和dist_sq(hull[i+1], hull[j])，更新max_dist。
5. 旋转基准边到下一条，重复步骤3-4。

int rotatingCalipers(vector<Point>& hull) {
    int n = hull.size();
    if (n == 2) return dist_sq(hull[0], hull[1]);
    int max_dist = 0;
    int j = 1;
    for (int i = 0; i < n; i++) {
        Point a = hull[i], b = hull[(i+1)%n];
        Point dir = {b.y - a.y, a.x - b.x}; // 垂直方向向量
        while (true) {
            Point c = hull[j], d = hull[(j+1)%n];
            int cross_val = cross(dir, {c.x - a.x, c.y - a.y});
            if (cross_val > 0) break; // 当前j已是最远
            max_dist = max(max_dist, dist_sq(a, c));
            max_dist = max(max_dist, dist_sq(b, c));
            j = (j + 1) % n;
        }
    }
    return max_dist;
}

步骤3：距离平方计算

为避免浮点数精度问题，直接计算距离的平方：

int dist_sq(const Point& a, const Point& b) {
    int dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}

优化与注意事项

1. 凸包去重：确保凸包顶点不重复，否则可能导致无限循环。
2. 方向向量处理：旋转卡壳中，方向向量需正确计算（垂直于基准边）。
3. 边界条件：当凸包为线段（n=2）时，直接返回两点距离平方。
4. 时间复杂度：凸包计算O(N log N)，旋转卡壳O(N)，总体O(N log N)。

实际应用与扩展

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

• 最小面积/周长矩形包围凸包。
• 凸包直径（最远点对）。
• 凸包宽度（最窄处距离）。
• 点集的极值点（最左、最右、最高、最低点）。

代码完整示例

#include <bits/stdc++.h>
using namespace std;
struct Point { int x, y; };
int cross(const Point& o, const Point& a, const Point& b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
vector<Point> convexHull(vector<Point>& points) {
    sort(points.begin(), points.end(), [](Point a, Point b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });
    vector<Point> hull;
    for (int phase = 0; phase < 2; phase++) {
        int start = hull.size();
        for (auto& p : points) {
            while (hull.size() >= start + 2 && 
                   cross(hull[hull.size()-2], hull.back(), p) <= 0)
                hull.pop_back();
            hull.push_back(p);
        }
        hull.pop_back();
        reverse(points.begin(), points.end());
    }
    return hull;
}
int dist_sq(const Point& a, const Point& b) {
    int dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}
int rotatingCalipers(vector<Point>& hull) {
    int n = hull.size();
    if (n == 2) return dist_sq(hull[0], hull[1]);
    int max_dist = 0;
    int j = 1;
    for (int i = 0; i < n; i++) {
        Point a = hull[i], b = hull[(i+1)%n];
        Point dir = {b.y - a.y, a.x - b.x};
        while (true) {
            Point c = hull[j], d = hull[(j+1)%n];
            int cross_val = cross(a, b, c); // 简化：用基准边(a,b)与c的叉积
            if (cross_val * cross(a, b, d) >= 0) break; // 更精确的判断
            max_dist = max(max_dist, dist_sq(a, c));
            max_dist = max(max_dist, dist_sq(b, c));
            j = (j + 1) % n;
        }
    }
    return max_dist;
}
int main() {
    int n;
    cin >> n;
    vector<Point> points(n);
    for (auto& p : points) cin >> p.x >> p.y;
    vector<Point> hull = convexHull(points);
    cout << rotatingCalipers(hull) << endl;
    return 0;
}

总结

POJ-2187 Beauty Contest问题通过旋转卡壳算法高效解决，其核心在于利用凸包的几何性质将问题规模从O(N^2)降至O(N log N)。开发者需掌握凸包计算与旋转卡壳的动态遍历技巧，同时注意边界条件与精度处理。该算法不仅适用于竞赛编程，也可扩展至计算机图形学、机器人路径规划等领域，具有极高的实用价值。