#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,inf=0x7f7f7f7f;
int n;
struct Point
{
double x,y;
}a[N],t[N];
bool cmp1(Point A,Point B)
{
if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
}
bool cmp2(Point A,Point B)
{
return A.y<B.y;
}
double dis(Point A,Point B)
{
double x=B.x-A.x,y=B.y-A.y;
return sqrt(x*x+y*y);
}
double solve(int l,int r)
{
double d=inf;
if(l==r) return d;
if(l+1==r) return dis(a[l],a[r]);
int mid=(l+r)>>1;
d=min(solve(l,mid),solve(mid+1,r));
int tot=0;
for(int i=l;i<=r;i++)
if(fabs(a[i].x-a[mid].x)<d)
t[++tot]=a[i];
sort(t+1,t+tot+1,cmp2);
for(int i=1;i<tot;i++)
for(int j=i+1;j<=tot;j++)
{
if(t[j].y-t[i].y>=d) break;
d=min(d,dis(t[i],t[j]));
}
return d;
}
int main ()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp1);
printf("%.4lf",solve(1,n));
return 0;
}
标签:return,min,int,Point,mid,最近,solve,平面
From: https://www.cnblogs.com/zhouruoheng/p/18437231