反手一只MJJ @ 2019-07-25 11:54:26
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<math.h>
using namespace std;
struct note{
double x,y;
friend bool operator < (note a,note A){
if(a.x==A.x)
return a.y>A.y;
return a.x<A.x;
}//x小的排前,x同则y大排前
}dian[200002]={0};//点
int n;
inline double minn(double a,double A){if(A-a>0)return a;return A;}
inline double dist(int l,int r){
double X=(dian[l].x-dian[r].x)*(dian[l].x-dian[r].x);
double Y=(dian[l].y-dian[r].y)*(dian[l].y-dian[r].y);
return sqrt(Y+X);
}//算距离
inline double dct(int l,int r){
if(r-l==1){return 100000007;}
if(r-l==2){return dist(l+1,r);}//二分的两种情况
int mid=(l+r)>>1;
double d1=dct(l,mid);//算二分左边
double d2=dct(mid,r);//算二分右边
double d=minn(d1,d2);
double tmp=100000007;//下面是算二分中间4或3个点,共4条或2条边。
if(mid-l==2){
tmp=minn(tmp,dist(mid-1,mid+2));
tmp=minn(tmp,dist(mid-1,mid+1));
}
tmp=minn(tmp,dist(mid,mid+1));
tmp=minn(tmp,dist(mid,mid+2));
return minn(d,tmp);
}
int main(){
n=rd;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&dian[i].x,&dian[i].y);
sort(dian+1,dian+1+n);
printf("%0.4lf",dct(0,n));
return 0;
}
感谢巨佬DAQ
by 白菜道士 @ 2019-08-25 20:54:28
@反手一只MJJ 看我的题解