我是用二分做的,不知道为什么错了。
#include <bits/stdc++.h>
using namespace std;
int n;
struct node
{
double x,y;
bool operator <(const node z)const
{
return x<z.x;
}
} a[400005],b[400005];
double dist(node x,node y)
{
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double dfs(int l,int r)
{
if(l>=r)
return 1e20;
int mid=(l+r)>>1,len=0;
double res=min(dfs(l,mid),dfs(mid+1,r)),mid_x=a[mid].x;
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
if(a[i].y<=a[j].y)
b[k++]=a[i++];
else
b[k++]=a[j++];
while(i<=mid) b[k++]=a[i++];
while(j<=r) b[k++]=a[j++];
for(i=l; i<=r; i++)
a[i]=b[i];
for(i=l; i<=r; i++)
{
if(a[i].x<=mid_x+res+1e-6&&a[i].x>=mid_x-res-1e-6)
b[++len]=a[i];
}
for(i=1; i<=len; i++)
for(j=i+1; j<=len&&b[j].y-b[i].y<=res; j++)
res=min(res,dist(b[i],b[j]));
return res;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,j;
cin>>n;
for(i=1; i<=n; i++)
cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1);
printf("%.4f\n",dfs(1,n));
return 0;
}