题解 P1429 【平面最近点对（加强版）】

Cesare · 2019-01-04 08:21:42 · 题解

此处使用了置顶题解的方法，建议搭配食用。

就是先随机旋转，然后根据横坐标排一遍序，枚举后五个点。

复杂度O(nlogn)

#include<bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;

ll n;
double ans=0x7f7f7f7f7f7f;

struct node {
    double x,y;
}p[200010];

inline bool cmp(node a,node b){return a.x<b.x;}

inline double dis(node a,node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

inline int read(){
    ll ans=0;bool f=0;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())f^=(ch=='-');
    for(;isdigit(ch);ch=getchar())ans=(ans<<3)+(ans<<1)+(ch^48);
    return f? -ans: ans;
}

int main(){
    n=read();
    for(re int i=1;i<=n;i++){
        double xx,yy;
        scanf("%lf%lf",&p[i].x,&p[i].y);
        xx=p[i].x*cos(422)-p[i].y*sin(422);//旋转公式
        yy=p[i].x*sin(422)+p[i].y*cos(422);//转两次
        p[i].x=xx,p[i].y=yy;
    }
    sort(p+1,p+n+1,cmp);
    for(re int i=1;i<=n;i++){
        ans=(ans>dis(p[i+1],p[i]))? dis(p[i+1],p[i]): ans;//枚举可行的点
        ans=(ans>dis(p[i+2],p[i]))? dis(p[i+2],p[i]): ans;
        ans=(ans>dis(p[i+3],p[i]))? dis(p[i+3],p[i]): ans;
        ans=(ans>dis(p[i+4],p[i]))? dis(p[i+4],p[i]): ans;
        ans=(ans>dis(p[i+5],p[i]))? dis(p[i+5],p[i]): ans;
    }
    printf("%.4lf\n",ans);
    return 0;
}