分析
我们可以枚举每一个点算它的最近点
估价函数应该分为3种情况计算：
大于max，小于min，位于min和max之间
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define int long long
const int inf = 1e18;
struct kd {
int d[],mx[],mn[],le,ri,id;
};
kd t[],now;
int n,m,root,wh,Ans=inf,sum,x[],y[];
inline bool operator < (kd a,kd b){
return a.d[wh]<b.d[wh];
}
inline void up(int rt){
for(int i=;i<;i++){
t[rt].mn[i]=min(t[rt].mn[i],min(t[t[rt].le].mn[i],t[t[rt].ri].mn[i]));
t[rt].mx[i]=max(t[rt].mx[i],max(t[t[rt].le].mx[i],t[t[rt].ri].mx[i]));
}
}
inline void build(int &x,int le,int ri,int wwh){
wh=wwh;
int mid=(le+ri)>>;
x=mid;
nth_element(t+le,t+x,t+ri+);
for(int i=;i<;i++)
t[x].mn[i]=t[x].mx[i]=t[x].d[i];
if(le<x)build(t[x].le,le,mid-,wwh^);
if(ri>x)build(t[x].ri,mid+,ri,wwh^);
up(x);
}
inline int getd(kd a,kd b){
return (a.d[]-b.d[])*(a.d[]-b.d[])+(a.d[]-b.d[])*(a.d[]-b.d[]);
}
inline int calc(int x){
if(!x)return inf;
int res=;
for(int i=;i<;i++){
if(now.d[i]<t[x].mn[i])res+=(now.d[i]-t[x].mn[i])*(now.d[i]-t[x].mn[i]);
else if(now.d[i]>t[x].mx[i])res+=(now.d[i]-t[x].mx[i])*(now.d[i]-t[x].mx[i]);
}
return res;
}
inline void qurey(int x){
if(!x)return;
int dl=calc(t[x].le),dr=calc(t[x].ri),d=getd(t[x],now);
if(d!=&&d<Ans)Ans=d;
if(d==)sum++;
if(dl<dr){
if(dl<Ans)qurey(t[x].le);
if(dr<Ans)qurey(t[x].ri);
}else {
if(dr<Ans)qurey(t[x].ri);
if(dl<Ans)qurey(t[x].le);
}
}
signed main(){
int i,j,k;
t[].mn[]=t[].mn[]=inf;
t[].mx[]=t[].mx[]=-inf;
scanf("%lld",&n);
for(i=;i<=n;i++){
scanf("%lld%lld",&x[i],&y[i]);
t[i].d[]=x[i],t[i].d[]=y[i];
t[i].id=i;
}
build(root,,n,);
for(i=;i<=n;i++){
sum=;
now.d[]=x[i],now.d[]=y[i];
qurey(root);
if(sum>){
Ans=;
break;
}
}
double out=sqrt((double)Ans);
printf("%0.4lf\n",out);
return ;
}