Kclz @ 2019-12-03 19:45:17
实在看不出来
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
int n,temp[1000001]={};
double minn=1000000000;
struct p{
double x,y;
}cord[200001],pt[200001];
bool cmp1(p a,p b){
if(a.x==b.x){
if(a.y>b.y){
return 0;
}
return 1;
}else{
return a.x<b.x;
}
}
bool cmp2(p a,p b){
if(a.y==b.y){
if(a.x>b.x){
return 0;
}
return 1;
}else{
return a.y<b.y;
}
}
double abs(double a,double b){
return (a>b)?a-b:b-a;
}
double dist(double ax,double ay,double bx,double by){
return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
}
double divis(int l,int r){
if(l==r){
return 10000000000;
}
if(l+1==r){
double u=dist(cord[l].x,cord[l].y,cord[r].x,cord[r].y);
minn=(minn>u)?u:minn;
return u;
}
int mid=(l+r)/2,k=0;
double d1=divis(l,mid),d2=divis(mid,r);
minn=(minn>d1)?d1:minn;
minn=(minn>d2)?d2:minn;
d1=cord[mid].x-minn;
d2=cord[mid].x+minn;
for(int i=l;i<=r;i++){
if(pt[i].x>=d1&&pt[i].x<=d2){
temp[k]=i;
++k;
}
}
for(int t=0;t<k;t++){
for(int j=t+1;j<=t+6&&j<k;j++){
double a=pt[temp[t]].y,b=pt[temp[j]].y;
double dis=dist(pt[temp[t]].x,a,pt[temp[j]].x,b);
minn=(minn>dis)?dis:minn;
if(abs(a,b)>minn){
break;
}
}
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lf%lf",&cord[i].x,&cord[i].y);
pt[i].x=cord[i].x;
pt[i].y=cord[i].y;
}
sort(cord,cord+n,cmp1);
sort(pt,pt+n,cmp2);
divis(0,n-1);
printf("%.4lf",minn);
return 0;
}