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

· · 题解

题意

给出平面上的 n 个点，求出 n 个点中距离最远的点对。

题解

容易发现答案一定在这些点的凸包上，所以我们先求凸包。但是如果直接枚举点求答案，时间复杂的还是可能退化到 O(n^2)。

我们改变一下枚举方案：我们按照逆时针枚举凸包的每一条边，再找距离这条边最远的点，然后用这个点到所枚举边的两端距离更新答案。当枚举下一条边时，我们发现有贡献的点也在按照枚举边的方向旋转，这意味着我们不需要枚举所有的点对，每次只需要逆时针找到距离所枚举边最远的点，用它与所枚举边的两端的距离更新答案，即只需要在枚举边的同时再枚举一遍点即可。

所以时间复杂度 O(n)？没这么优秀，排序是 O(n\log n) 的，所以总时间复杂度为 O(n\log n)。

代码


#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=1e6+5;
int T;
struct Point{int x,y,id;}p[N],s[N];
bool operator ==(Point a,Point b){return (a.x==b.x && a.y==b.y);}
int dis(Point a,Point b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}//计算两点距离。这里我们直接用整数计算，与实际等价，开根还会掉精度
int Dis(Point a,Point b,Point c){return abs((b.y-a.y)*c.x+(a.x-b.x)*c.y+a.y*b.x-a.x*b.y);}//点到边的距离，因为比较时是对同一条边进行比较，所以不用除以边向量的模长。
int mul(Point a1,Point a2,Point b1,Point b2){return (a1.x-a2.x)*(b1.y-b2.y)-(a1.y-a2.y)*(b1.x-b2.x);}
bool cmp(Point a,Point b){int tmp=mul(a,p[0],b,p[0]);return (tmp>0 || (tmp==0 && dis(a,p[0])<dis(b,p[0])));}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> T;
    while(T--){
        int n,cnt=0ll,Max=-1ll,now=1ll,ans1=0ll,ans2=1ll;
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> p[i].x >> p[i].y,p[i].id=i;
            if(p[i].y<p[0].y) swap(p[i],p[0]);
            else if(p[i].y==p[0].y && p[i].x<p[0].x) swap(p[i],p[0]);
        }
        n=unique(p+1,p+n)-p,sort(p+1,p+n,cmp),s[0]=p[0];
        for(int i=1;i<n;s[++cnt]=p[i++])
            while(cnt && mul(s[cnt-1],s[cnt],s[cnt],p[i])<=0) cnt--;//求凸包
        if(cnt==0){cout <<"0 1\n";continue;}
        if(cnt==1){cout << s[0].id <<" "<< s[1].id <<"\n";continue;}//注意特判
        for(int i=0;i<=cnt;i++) s[i+cnt+1]=s[i];
        for(int i=0;i<=cnt;i++){
            while(Dis(s[i],s[i+1],s[now])<=Dis(s[i],s[i+1],s[now+1])) now++;//找到距离第i条边最远的点
            int dis1=dis(s[i],s[now]),dis2=dis(s[i+1],s[now]);
            if(dis1>Max) Max=dis1,ans1=s[now].id,ans2=s[i].id;
            if(dis2>Max) Max=dis2,ans1=s[now].id,ans2=s[i+1].id;//更新答案
        }//旋转卡壳
        cout << ans1 <<" "<< ans2 <<"\n";
    }
    return 0;
}