https://www.luogu.com.cn/problem/P1452 cpp题解

<think>题目要求我们使用中文回答问题，并在回答后提出3-5个相关问题，且第一行必须完整输出“§§相关问题§§”，然后紧接着列出问题，禁止换行分散。 首先，我需要理解用户给出的问题：用户提供了一个洛谷题目的链接（P1452），要求提供C++题解。因此，我的任务是编写解决这个题目的C++代码，并解释思路。 题目链接：https://www.luogu.com.cn/problem/P1452 题目名称：Beauty Contest（旋转卡壳求凸包直径） 题目大意：给定平面上的一些点，求最远点对的距离的平方。 解题思路： 1. 求凸包：使用Andrew算法或Graham扫描法求凸包。 2. 旋转卡壳：在凸包上求直径（最远点对）。 步骤： 1. 读入点集。 2. 对点集进行排序（按x从小到大，x相同则按y从小到大）。 3. 求凸包（下凸包和上凸包）。 4. 使用旋转卡壳算法在凸包上寻找距离最远的两个点。 5. 输出距离的平方。 注意：题目要求输出距离的平方（避免浮点数运算，但本题输入是整数，所以平方也是整数）。 代码实现： - 凸包求法：使用Andrew算法。 - 旋转卡壳：使用双指针法，遍历凸包上的点，利用叉积和点积的性质。 现在，编写C++代码，并添加必要的注释。 代码完成后，按照要求提出3-5个相关问题。 相关问题应该与题目相关，例如凸包、旋转卡壳、计算几何的基础知识等。 下面开始编写代码：</think>### 洛谷 P1452 "Beauty Contest" C++ 题解 **题目大意**：给定平面上的 $n$ 个点，求最远点对距离的平方（$1 \leq n \leq 5 \times 10^4$）。 **核心算法**：Andrew 凸包算法 + 旋转卡壳求直径 **代码实现**： ```cpp #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; struct Point { ll x, y; Point(ll x = 0, ll y = 0) : x(x), y(y) {} bool operator<(const Point &p) const { return x < p.x || (x == p.x && y < p.y); } Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); } }; // 叉积 ll cross(const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; } // 距离平方 ll dist2(const Point &a, const Point &b) { ll dx = a.x - b.x, dy = a.y - b.y; return dx * dx + dy * dy; } // 求凸包（Andrew算法） vector<Point> convexHull(vector<Point> &p) { int n = p.size(), k = 0; if (n <= 1) return p; vector<Point> hull(2 * n); sort(p.begin(), p.end()); // 下凸包 for (int i = 0; i < n; hull[k++] = p[i++]) while (k >= 2 && cross(hull[k-1]-hull[k-2], p[i]-hull[k-2]) <= 0) k--; // 上凸包 for (int i = n-2, t = k+1; i >= 0; hull[k++] = p[i--]) while (k >= t && cross(hull[k-1]-hull[k-2], p[i]-hull[k-2]) <= 0) k--; hull.resize(k - 1); return hull; } // 旋转卡壳求凸包直径平方 ll rotatingCalipers(vector<Point> &hull) { int n = hull.size(); if (n == 1) return 0; if (n == 2) return dist2(hull[0], hull[1]); ll ans = 0; for (int i = 0, j = 1; i < n; ++i) { // 移动对踵点直到距离不再增加 while (abs(cross(hull[(i+1)%n]-hull[i], hull[j]-hull[i])) < abs(cross(hull[(i+1)%n]-hull[i], hull[(j+1)%n]-hull[i]))) { j = (j + 1) % n; } ans = max(ans, dist2(hull[i], hull[j])); } return ans; } 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); cout << rotatingCalipers(hull) << endl; return 0; } ``` **算法解析**： 1. **凸包构建**（Andrew 算法） - 排序点集后，分别计算下凸包和上凸包 - 利用叉积判断点的走向（$\leq 0$ 保留共线点） 2. **旋转卡壳求直径** - 对凸包上的点，用双指针 $i$ 和 $j$ 遍历 - 关键优化：当 $j$ 移动到使三角形面积（叉积绝对值）最大时，更新最远距离 - 时间复杂度：$O(n)$（凸包 $O(n \log n)$，卡壳 $O(n)$）