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

引言

POJ（北京大学在线判题系统）中的2187号题目”Beauty Contest”是一道经典的计算几何问题，其核心在于求解凸包上最远点对的距离。这一问题的解法不仅考验编程者对几何算法的理解，更是对算法效率与实现细节的双重挑战。旋转卡壳（Rotating Calipers）作为一种高效的几何算法，因其简洁性和高效性，成为解决此类问题的首选方法。本文将围绕这一算法，深入剖析其原理与实现，为开发者提供一条清晰的学习路径。

问题背景

Beauty Contest问题描述

题目要求在一组二维平面的点集中，找到距离最远的两个点，计算它们之间的欧几里得距离。直接暴力枚举所有点对虽然可行，但时间复杂度为O(n²)，对于大规模数据集显然不适用。因此，需要一种更高效的算法。

凸包与最远点对

凸包是包含所有给定点的最小凸多边形。一个关键性质是，最远点对必定位于凸包的顶点上。因此，问题可以转化为在凸包顶点中寻找最远点对，从而将问题规模从n个点缩小到凸包的m个顶点（m ≤ n）。

旋转卡壳算法原理

凸包的构建

在应用旋转卡壳之前，首先需要构建给定点集的凸包。常用的凸包构建算法有Graham Scan和Andrew’s Monotone Chain算法，两者时间复杂度均为O(n log n)。这里以Andrew’s Monotone Chain算法为例，简要说明其步骤：

1. 排序：将所有点按x坐标升序排序，若x坐标相同则按y坐标升序排序。
2. 构建下凸包：从左到右遍历排序后的点，维护一个栈结构，确保每次加入新点时，栈顶元素与新点构成的线段不会使凸包出现“凹陷”。
3. 构建上凸包：从右到左遍历排序后的点，同样维护栈结构，构建上凸包。
4. 合并上下凸包：去除重复的起点和终点，得到完整的凸包。

旋转卡壳的基本思想

旋转卡壳算法的核心在于利用两条平行且垂直于某方向的直线“卡”住凸包，通过旋转这两条直线，逐次检查每对相邻边上的最远点对，从而找到全局最远点对。具体步骤如下：

1. 初始化：选择凸包上的一个点作为起点，计算其到其他所有点的距离，找到初始的最远点对。
2. 旋转直线：以起点为轴心，旋转一条直线（卡壳），每次旋转后，计算新直线与凸包边的交点，并更新当前最远点对。
3. 更新最远点对：在旋转过程中，持续比较并记录遇到的最远点对距离。
4. 终止条件：当直线旋转一周回到起点时，算法终止，此时记录的最远点对即为所求。

算法细节与优化

• 角度排序：为了高效旋转卡壳，可以将凸包顶点按极角排序，这样旋转过程可以转化为顺序访问顶点。
• 距离计算：在旋转过程中，利用向量叉积和点积可以高效计算点到直线的距离，避免直接计算欧几里得距离带来的浮点数运算误差。
• 提前终止：在某些情况下，可以提前终止旋转过程，例如当剩余未检查的边不可能产生更远点对时。

代码实现与解析

以下是一个基于旋转卡壳算法的POJ 2187 Beauty Contest问题的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) {}
    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 lowerHullSize = H.size();
    for (int i = n - 2; i >= 0; --i) {
        while (H.size() > lowerHullSize && 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>& 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 nextI = hull[(i + 1) % n];
        while (abs(cross(hull[i], nextI, hull[j])) <= abs(cross(hull[i], nextI, hull[(j + 1) % n]))) {
            j = (j + 1) % n;
        }
        maxDist = max(maxDist, dist(hull[i], hull[j]));
        maxDist = max(maxDist, dist(nextI, hull[j]));
    }
    return maxDist;
}
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> hull = convexHull(P);
    double maxDist = rotatingCalipers(hull);
    cout << (int)(maxDist * maxDist) << endl; // 题目要求输出距离的平方
    return 0;
}

代码解析

1. 凸包构建：convexHull函数使用Andrew’s Monotone Chain算法构建凸包，通过排序和栈操作确保凸包的正确性。
2. 距离计算：dist函数计算两点之间的欧几里得距离。
3. 旋转卡壳：rotatingCalipers函数实现旋转卡壳算法，通过遍历凸包顶点，利用叉积判断最远点对，并更新最大距离。
4. 主函数：读取输入点集，构建凸包，调用旋转卡壳算法求解最远点对距离，并输出结果（题目要求输出距离的平方）。

实际应用与优化建议

实际应用

旋转卡壳算法不仅适用于求解最远点对问题，还可以扩展到求解凸包直径、最小面积/周长矩形包围等几何问题。在计算机图形学、地理信息系统（GIS）、机器人路径规划等领域有广泛应用。

优化建议

1. 浮点数精度：在计算过程中，注意浮点数精度问题，可以使用长整型或高精度库来避免误差。
2. 并行计算：对于大规模点集，可以考虑并行计算凸包和旋转卡壳过程，提高算法效率。
3. 预处理：在应用旋转卡壳之前，对点集进行预处理，如去除重复点、简化点集等，可以减少不必要的计算。

结论

POJ 2187 Beauty Contest问题通过旋转卡壳算法得到了高效解决。本文详细阐述了凸包的构建、旋转卡壳算法的原理与实现，并通过代码示例展示了算法的具体应用。旋转卡壳算法以其简洁性和高效性，在计算几何领域占有重要地位。对于开发者而言，掌握这一算法不仅有助于解决类似问题，更能提升对几何算法的理解和应用能力。