G55 平面最近点对 分治算法【计算几何】

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct node{double x,y;}p[N];
bool cmp(node p1,node p2){if(p1.x!=p2.x)return p1.x<p2.x;else return p1.y<p2.y;}
double dis(node p1,node p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}
double solve(int l, int r)
{
    if (l == r) return 1e18;
    int mid = (l + r) >> 1;
    double ans = min( solve(l,mid) , solve(mid+1, r) );
    int tl = mid, tr = mid;
    while (tl >= l && p[mid].x - p[tl].x < ans) tl--; tl++;
    while (tr <= r && p[tr].x - p[mid].x < ans) tr++; tr--;
    for (int i = tl; i < tr; i++)
        for (int j = i + 1; j <= tr; j++)
            ans =min(ans, dis(p[i], p[j]));
    return ans;
}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
    sort(p+1,p+n+1,cmp);
    printf("%.4lf\n",solve(1,n));
    return 0;
}