题解：P16223 【模板】旋转卡壳/最远点对

· · 题解

我们充分发扬人类智慧：

将所有点全部绕原点旋转同一个角度，然后按 x^2+y^2 排序。

根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定会离得比较远。

所以我们只取每个点距离大于 1000 的两端的其他点来计算答案。

这样速度快得飞起，在 n=5\times10^5 时都可以在 500 ms 内卡过。

欸不对搞错了。

P16223 【模板】旋转卡壳/最远点对

前置知识

二维凸包，如何求二维凸包。

题意简述

给定 T 组数据，每组给出二维平面上的 N 个点，求一对下标 (i,j)（i\neq j），使得它们之间的欧几里得距离最大。输出任意一组满足条件的下标。

思路

求最远点对可以化成求凸包的直径。显然最远点对一定位于点集的凸包顶点上。

::::info[证明]

设凸包为 K，直径为 d = \max_{x,y \in K} \|x-y\|。取 (A,B) 使 \|A-B\|=d。

固定 B，定义 f(X)=\|X-B\|。由三角不等式，f 是凸函数：

若 $A$ 非顶点，则 $A=\lambda A_1+(1-\lambda)A_2$，其中 $0<\lambda<1$。 于是 $d=f(A) \le \lambda f(A_1)+(1-\lambda)f(A_2)$。 因 $d$ 是全局最大，$f(A_1),f(A_2)\le d$，故必须 $f(A_1)=f(A_2)=d$。 所以可将 $A$ 替换为 $A_1$ 或 $A_2$，距离不变。重复此过程，最终得到顶点 $A'$，使 $\|A'-B\|=d$。 固定 $A'$，定义 $g(Y)=\|A'-Y\|$，同理，若 $B$ 非顶点，可替换为凸组合中的点，距离保持 $d$，最终得到顶点 $B'$，使 $\|A'-B'\|=d$。 故存在两个顶点 $A',B'$ 达到直径 $d$。证毕。 :::: 直观上，距离函数 $\operatorname{dist}(p,q)=\sqrt{(x_p-x_q)^2+(y_p-y_q)^2}$ 是凸函数，其最大值在凸多边形的顶点处取得（事实上，对于任意点集，最远点对必为凸包的对踵点）。因此，我们只需计算点集的凸包，然后在凸包顶点之间寻找最大距离。 ### 如何求凸包直径 对于凸包上的每条边 $e_i = (P_i, P_{i+1})$，找到距离该边最远的顶点 $P_j$（称为对踵点）。顺时针/逆时针遍历所有边，计算它们的对踵点，显然，对踵点会跟着枚举的边顺时针/逆时针旋转，利用双指针枚举即可。 具体的，先使用 Andrew 单调链算法构建凸包，再利用双指针实现旋转卡壳求直径即可。 ## [P1452 [USACO03FALL] Beauty Contest G](https://www.luogu.com.cn/problem/P1452) 本题弱化版，原模板题，建议读者先通过本题后再来挑战[本题](https://www.luogu.com.cn/problem/P16223)。 ```cpp #include <bits/stdc++.h> #define N 100010 using namespace std; typedef long long LL; //十年OI一场空，不开long long见祖宗 struct point{ int x , y; point(){} point(int x_ , int y_){ x = x_ , y = y_; } bool operator < (const point &a) const{ if(x != a.x) return x < a.x; return y < a.y; } point operator - (const point &a) const{ return point(x - a.x , y - a.y); } }p[N] , st[N]; int n; int cross(point a , point b){ return a.x * b.y - a.y * b.x; } int dis(point a , point b){ return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); } int main(){ //freopen(".in" , "r" , stdin); //freopen(".out" , "w" , stdout); scanf("%d" , &n); for(int i = 1 ; i <= n ; ++i){ int x , y; scanf("%d%d" , &x , &y); p[i] = point(x , y); } sort(p + 1 , p + n + 1); int top = 0; for(int i = 1 ; i <= n ; ++i){ while(top > 1 && cross(st[top] - st[top - 1] , p[i] - st[top - 1]) <= 0) top -= 1; st[++top] = p[i]; } int k = top; for(int i = n - 1 ; i >= 1 ; --i){ while(top > k && cross(st[top] - st[top - 1] , p[i] - st[top - 1]) <= 0) top -= 1; st[++top] = p[i]; } int m = top - 1; if(m == 2){ printf("%lld\n" , dis(st[1] , st[2])); return 0; } int ans = 0; int j = 2; for(int i = 1 ; i <= m ; ++i){ point cur = st[i % m + 1] - st[i]; while(cross(cur , st[j % m + 1] - st[i]) > cross(cur , st[j] - st[i])) j = j % m + 1; ans = max(ans , dis(st[i] , st[j])); ans = max(ans , dis(st[i % m + 1] , st[j])); } printf("%lld\n" , ans); return 0; } ``` ## [P16223 【模板】旋转卡壳/最远点对](https://www.luogu.com.cn/problem/P16223) ~~警示后人之一定不要直接从 [P1452 [USACO03FALL] Beauty Contest G](https://www.luogu.com.cn/problem/P1452) 直接复制代码过来，你会改的很崩溃。~~ 一些实现细节： 1. [P1452](https://www.luogu.com.cn/problem/P1452) 中保证所有点的坐标两两不同，但是本题没有，所以一定要记得去重，否则 Andrew 构建的凸包会错的离谱； 2. 本题要求输出**原先的点的编号**，排序的时候请维护原先的下标； 3. 本题从 [P1452](https://www.luogu.com.cn/problem/P1452) 的 $|x|,|y|\le 10^4$ 扩大到了 $|x_i|, |y_i| \le 10^9$，要开 `long long`。 ```cpp #include <bits/stdc++.h> #define N 500005 using namespace std; typedef long long LL; //十年OI一场空，不开long long见祖宗 struct point{ int x , y , id; point(){} point(int x_ , int y_ , int id_){ x = x_ , y = y_ , id = id_; } bool operator < (const point &a) const{ if(x != a.x) return x < a.x; if(y != a.y) return y < a.y; return id < a.id; } bool operator == (const point &a) const{ return x == a.x && y == a.y; } point operator - (const point &a) const{ return point(x - a.x , y - a.y , 0); } }p[N] , q[N] , st[N]; int n , T; LL cross(point a , point b){ return (LL)a.x * b.y - (LL)a.y * b.x; } LL dis(point a , point b){ return (LL)(a.x - b.x) * (a.x - b.x) + (LL)(a.y - b.y) * (a.y - b.y); } inline void solve(){ scanf("%d" , &n); for(int i = 1 ; i <= n ; ++i){ int x , y; scanf("%d%d" , &x , &y); p[i] = point(x , y , i - 1); } sort(p + 1 , p + n + 1); int uniq = 0; for(int i = 1 ; i <= n ; ++i){ if(i == 1 || !(p[i] == p[i - 1])) q[++uniq] = p[i]; } if(uniq == 1){ printf("%d %d\n" , p[1].id , p[2].id); return; } int top = 0; for(int i = 1 ; i <= uniq ; ++i){ while(top > 1 && cross(st[top] - st[top - 1] , q[i] - st[top - 1]) <= 0) top -= 1; st[++top] = q[i]; } int k = top; for(int i = uniq - 1 ; i >= 1 ; --i){ while(top > k && cross(st[top] - st[top - 1] , q[i] - st[top - 1]) <= 0) top -= 1; st[++top] = q[i]; } int m = top - 1; if(m == 2){ printf("%d %d\n" , st[1].id , st[2].id); return; } LL ans = 0; int j = 2 , ansi = 0 , ansj = 0; for(int i = 1 ; i <= m ; ++i){ point cur = st[i % m + 1] - st[i]; while(cross(cur , st[j % m + 1] - st[i]) > cross(cur , st[j] - st[i])) j = j % m + 1; LL d1 = dis(st[i] , st[j]); LL d2 = dis(st[i % m + 1] , st[j]); if(d1 > ans) ans = d1 , ansi = st[i].id , ansj = st[j].id; if(d2 > ans) ans = d2 , ansi = st[i % m + 1].id , ansj = st[j].id; } printf("%d %d\n" , ansi , ansj); return; } int main(){ scanf("%d" , &T); while(T--) solve(); return 0; } ``` ::::info[[人类智慧永垂不朽](https://www.luogu.com.cn/record/286548239)] ```cpp #include <bits/stdc++.h> using namespace std; typedef long long LL; //十年OI一场空，不开long long见祖宗 using namespace std; typedef long long LL; const int N = 500010; const int STEP = 300; struct point { double x, y; int id; } a[N]; int T, n; double maxn; int ans1, ans2; inline double dis(const point& p, const point& q){ double dx = p.x - q.x; double dy = p.y - q.y; return dx * dx + dy * dy; } inline bool cmp(const point& p, const point& q){ return p.x * p.x + p.y * p.y < q.x * q.x + q.y * q.y; } inline void upd(const point& p, const point& q){ double d = dis(p, q); if (d > maxn) { maxn = d; ans1 = p.id; ans2 = q.id; } } int main(){ //freopen(".in" , "r" , stdin); //freopen(".out" , "w" , stdout); scanf("%d", &T); while(T--){ scanf("%d", &n); for(int i = 1 ; i <= n ; i++){ scanf("%lf%lf" , &a[i].x , &a[i].y); a[i].id = i - 1; } maxn = -1.0; ans1 = 0, ans2 = 1; if(n == 2){ printf("0 1\n"); continue; } sort(a + 1, a + n + 1, cmp); for(int i = 1; i <= n; i++) { int end1 = min(n, i + STEP); for (int j = i + 1 ; j <= end1 ; j++) upd(a[i], a[j]); int start2 = max(i + 1, n - STEP + 1); for(int j = start2 ; j <= n ; j++) upd(a[i], a[j]); } printf("%d %d\n", ans1, ans2); } return 0; } ``` ::::