洛谷p1429 平面最近点对

#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int N=200050,INF=1<<30;
struct  {double x,y;} t[N];
vector<int> w;
bool cmp(dot a,dot b) {return a.x==b.x?a.y<b.y:a.x<b.x;}
bool check(int a,int b) {return t[a].y<t[b].y;}
double sqr(double x) {return x*x;}
double dist(dot a,dot b) {return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
double calc(int l,int r)
{
    double ret=INF;
    if (l==r) return ret;
    int mid=(l+r)>>1;
    ret=min(ret,min(calc(l,mid),calc(mid+1,r)));
    w.clear();
    for(int i=l;i<=r;i++)
        if (fabs(t[i].x-t[mid].x)<ret) w.push_back(i);
    sort(w.begin(),w.end(),check);
    for(int i=0;i<w.size();i++)
        for(int j=i+1;j<w.size()&&fabs(t[w[i]].y-t[w[j]].y)<ret;j++)
            ret=min(ret,dist(t[w[i]],t[w[j]]));
    return ret;	
}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&t[i].x,&t[i].y);
    sort(t+1,t+n+1,cmp);
    printf("%.4lf",calc(1,n));
    return 0;
}