引言

POJ-2187 Beauty Contest是一道经典的计算几何题目，要求在平面上给定的一组点中，找到距离最远的两个点。这类问题在计算机图形学、机器人路径规划、地理信息系统等领域有着广泛的应用。传统方法通过遍历所有点对计算距离，时间复杂度为O(n²)，当点数较多时效率极低。而旋转卡壳算法（Rotating Calipers）作为一种高效的几何工具，能够将时间复杂度优化至O(n)，特别适用于凸包上的最远点对求解。本文将围绕POJ-2187题目，详细讲解旋转卡壳算法的原理、实现步骤及优化技巧，帮助读者深入理解这一经典算法。

问题描述

POJ-2187 Beauty Contest的题目大意如下：给定平面上的n个点，要求找出其中距离最远的两个点，并输出它们的距离。输入为点的坐标，输出为最大距离值。由于最远点对必然位于凸包上，因此问题的关键在于如何高效地求解凸包，并在凸包上应用旋转卡壳算法找到最远点对。

旋转卡壳算法原理

旋转卡壳算法是一种用于解决凸包相关问题的几何算法，其核心思想是通过维护一组“卡壳”（即平行于坐标轴或特定方向的直线），逐步旋转并更新卡壳的位置，从而在凸包上找到所需的极值点。对于最远点对问题，旋转卡壳算法通过以下步骤实现：

1. 构造凸包：首先使用Graham扫描法或Andrew算法等构造给定点集的凸包。
2. 初始化卡壳：选择凸包上的一个点作为起点，并找到其最远的点（即凸包上的对踵点）。
3. 旋转卡壳：以起点为基准，逐步旋转卡壳，每次旋转后更新当前点与卡壳的交点，计算交点与当前点的距离，并记录最大值。
4. 终止条件：当卡壳旋转一周回到起点时，算法终止，此时记录的最大距离即为所求。

算法实现步骤

1. 构造凸包

构造凸包是旋转卡壳算法的前提。以Graham扫描法为例，其步骤如下：

• 选择y坐标最小的点作为基准点（若存在多个，选择x坐标最小的点）。
• 将其他点按与基准点的极角排序。
• 使用栈结构维护凸包上的点，依次处理排序后的点，若当前点与栈顶两点构成的线段为顺时针方向，则弹出栈顶元素，直到满足凸包条件。
• 最终栈中的点即为凸包的顶点。

2. 旋转卡壳求最远点对

在凸包构造完成后，应用旋转卡壳算法求最远点对：

• 初始化：选择凸包上的一个点作为起点P0，找到其最远的点PN（对踵点）。
• 旋转卡壳：以P0为基准，维护两条卡壳线，一条固定于P0，另一条逐步旋转。每次旋转后，计算当前卡壳线与凸包的交点Q，并计算P0与Q的距离。
• 更新最大值：在旋转过程中，不断更新记录的最大距离。
• 终止条件：当卡壳线旋转一周回到P0时，算法终止。

3. 代码实现

以下是一个简化的旋转卡壳算法实现（以C++为例）：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};
// 计算两点间距离
double dist(const Point &a, const Point &b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
// 凸包构造（Graham扫描法）
vector<Point> convexHull(vector<Point> &points) {
    int n = points.size();
    if (n <= 2) return points;
    // 按y坐标排序，y相同按x排序
    sort(points.begin(), points.end(), [](const Point &a, const Point &b) {
        return a.y < b.y || (a.y == b.y && a.x < b.x);
    });
    vector<Point> hull;
    hull.push_back(points[0]);
    hull.push_back(points[1]);
    for (int i = 2; i < n; ++i) {
        while (hull.size() >= 2) {
            Point p2 = hull.back();
            hull.pop_back();
            Point p1 = hull.back();
            if ((p2.x - p1.x) * (points[i].y - p1.y) - (p2.y - p1.y) * (points[i].x - p1.x) > 0) {
                hull.push_back(p2);
                break;
            }
        }
        hull.push_back(points[i]);
    }
    return hull;
}
// 旋转卡壳求最远点对
double rotatingCalipers(vector<Point> &hull) {
    int n = hull.size();
    if (n == 2) return dist(hull[0], hull[1]);
    double maxDist = 0;
    int j = 1;
    for (int i = 0; i < n; ++i) {
        Point &pi = hull[i];
        Point &pj = hull[j];
        while (abs((pj.x - pi.x) * (hull[(j + 1) % n].y - pi.y) - (pj.y - pi.y) * (hull[(j + 1) % n].x - pi.x)) < 
               abs((pj.x - pi.x) * (hull[j].y - pi.y) - (pj.y - pi.y) * (hull[j].x - pi.x))) {
            j = (j + 1) % n;
            pj = hull[j];
        }
        maxDist = max(maxDist, dist(pi, pj));
    }
    return maxDist;
}
int main() {
    int n;
    cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
    }
    vector<Point> hull = convexHull(points);
    double maxDist = rotatingCalipers(hull);
    printf("%.2f\n", maxDist);
    return 0;
}

优化技巧与注意事项

1. 凸包构造优化：使用Andrew算法构造凸包可能更高效，尤其是当点集较大时。
2. 浮点数精度：在计算距离和判断方向时，注意浮点数精度问题，避免使用等号判断。
3. 输入处理：确保输入点不重复，且凸包顶点数大于2。
4. 代码复用：将凸包构造和旋转卡壳算法封装为独立函数，提高代码复用性。

结论

POJ-2187 Beauty Contest问题通过旋转卡壳算法能够高效求解，其核心在于利用凸包的性质和旋转卡壳的几何特性，将时间复杂度优化至O(n)。本文详细讲解了旋转卡壳算法的原理、实现步骤及优化技巧，并通过代码示例展示了具体实现。对于从事计算几何、机器人路径规划等领域的开发者，掌握旋转卡壳算法具有重要的实际价值。