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

一、问题背景与概述

POJ - 2187题目名为“Beauty Contest”，实质上是一个经典的几何计算问题——在二维平面上给定一组点，要求找出其中距离最远的两个点。这类问题在计算几何领域被称为“最远点对问题”（Farthest Pair Problem），广泛应用于路径规划、图形处理、数据分析等领域。

最直接的解法是暴力枚举所有点对，计算其欧几里得距离，并记录最大值。这种方法的时间复杂度为O(n²)，当n较大时（如n>10⁵），其效率将显著下降。为此，人们提出了更高效的算法，其中“旋转卡壳”（Rotating Calipers）便是解决此类问题的经典方法之一，尤其适用于凸包（Convex Hull）上的最远点对搜索，其时间复杂度可降至O(n log n)（包含凸包构建时间）或O(n)（若凸包已给定）。

二、旋转卡壳算法原理

1. 凸包简介

旋转卡壳算法的前提是点集的凸包。凸包是指包含所有给定点且各边均不向内凹陷的最小凸多边形。构建凸包的过程通常采用Graham Scan或Andrew’s Monotone Chain等算法，时间复杂度为O(n log n)。

2. 旋转卡壳核心思想

旋转卡壳算法的核心在于利用凸包的性质，通过“卡壳”（即两条平行直线）的旋转来逐步检查可能的候选最远点对。具体步骤如下：

• 初始化：选择凸包上的一条边作为起始边，找到与该边相对的最远点（即该边垂直方向上的最远点）。
• 旋转：固定一条边，旋转另一条卡壳线（保持与固定边平行），直到遇到凸包的下一个顶点，此时更新最远点。
• 更新最远距离：在每次旋转过程中，计算当前卡壳线所夹两点间的距离，并更新全局最大值。
• 终止条件：当卡壳线旋转一周回到起始位置时，算法结束。

3. 为什么旋转卡壳有效？

旋转卡壳之所以有效，是因为凸包上的最远点对必然位于凸包的顶点上，且至少有一对最远点对是凸包的“反平行边”（即两条边在旋转过程中不会同时被卡壳线夹住）。通过旋转卡壳，我们可以高效地遍历所有可能的反平行边对，从而找到最远点对。

三、POJ - 2187问题解析

1. 问题描述

给定平面上的n个点，找出其中距离最远的两个点。

2. 输入输出

• 输入：第一行为整数n（2≤n≤50000），接下来n行，每行两个整数x, y，表示一个点的坐标。
• 输出：最远点对的距离，保留两位小数。

3. 解题步骤

1. 构建凸包：使用Graham Scan或Andrew’s Monotone Chain算法构建点集的凸包。
2. 应用旋转卡壳：在凸包上应用旋转卡壳算法，寻找最远点对。
3. 输出结果：计算并输出最远点对的距离。

四、代码实现与解析

以下是一个基于C++的旋转卡壳算法实现示例：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    bool operator<(const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
};
double 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>& P) {
    int n = P.size();
    if (n <= 1) return P;
    sort(P.begin(), P.end());
    vector<Point> H;
    for (int i = 0; i < n; ++i) {
        while (H.size() >= 2 && cross(H[H.size() - 2], H.back(), P[i]) <= 0)
            H.pop_back();
        H.push_back(P[i]);
    }
    int lower_hull_size = H.size();
    for (int i = n - 2; i >= 0; --i) {
        while (H.size() > lower_hull_size && cross(H[H.size() - 2], H.back(), P[i]) <= 0)
            H.pop_back();
        H.push_back(P[i]);
    }
    H.pop_back(); // 重复的起点
    return H;
}
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));
}
double rotatingCalipers(const vector<Point>& H) {
    int n = H.size();
    if (n == 2) return dist(H[0], H[1]);
    double max_dist = 0;
    int j = 1;
    for (int i = 0; i < n; ++i) {
        Point next_i = H[(i + 1) % n];
        while (abs(cross(H[i], next_i, H[j])) < abs(cross(H[i], next_i, H[(j + 1) % n]))) {
            j = (j + 1) % n;
        }
        max_dist = max(max_dist, dist(H[i], H[j]));
        max_dist = max(max_dist, dist(next_i, H[j]));
    }
    return max_dist;
}
int main() {
    int n;
    cin >> n;
    vector<Point> P(n);
    for (int i = 0; i < n; ++i) {
        cin >> P[i].x >> P[i].y;
    }
    vector<Point> H = convexHull(P);
    double max_dist = rotatingCalipers(H);
    cout << fixed << setprecision(2) << max_dist << endl;
    return 0;
}

代码解析

1. 结构体与辅助函数：定义Point结构体表示二维点，cross函数计算叉积，用于判断点的相对位置。
2. 凸包构建：convexHull函数使用Andrew’s Monotone Chain算法构建凸包。
3. 距离计算：dist函数计算两点间的欧几里得距离。
4. 旋转卡壳：rotatingCalipers函数实现旋转卡壳算法，通过旋转卡壳线寻找最远点对。
5. 主函数：读取输入，构建凸包，调用旋转卡壳算法，输出结果。

五、总结与展望

旋转卡壳算法以其高效性和简洁性在计算几何领域占有重要地位。通过本文的介绍与实现，读者不仅掌握了旋转卡壳算法的基本原理，还学会了如何将其应用于实际问题中。未来，随着计算几何问题的不断复杂化，旋转卡壳算法及其变种将在更多领域发挥重要作用，如三维空间的最远点对搜索、动态点集的最远点对维护等。