Pagini recente » Cod sursa (job #1609537) | Cod sursa (job #2575918) | Cod sursa (job #218930) | Cod sursa (job #2112268) | Cod sursa (job #432530)
Cod sursa(job #432530)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define Nmax 100005
#define INF 2000000000
using namespace std;
struct punct{ int x,y; } ;
punct a[Nmax];
int n,i;
int cmp(punct a, punct b){
return (a.x < b.x || (a.x==b.x && a.y<b.y));
}
inline double Minim( double x, double y){
return x<y ? x:y;
}
inline double abs( double x ){
return x > 0 ? x : -x;
}
inline double dist( int i,int j ){
return sqrt( (double) (a[i].x-a[j].x)*(a[i].x-a[j].x)
+ (double) (a[i].y-a[j].y)*(a[i].y-a[j].y) );
}
int aux[Nmax];
double dist_min(int st,int dr){
double d,d1,d2;
int i,j,mij;
if(st>=dr) return INF;
if(st==dr-1)
return dist(st,dr);
mij=st+(dr-st)/2;
d1=dist_min(st,mij);
d2=dist_min(mij+1,dr);
d=d1 < d2 ? d1 : d2;
aux[0]=0;
for(i=st;i<=dr;++i)
if( abs(a[i].x-a[mij].x) <= d )
aux[++aux[0]]=i;
for(i=1;i<=aux[0];++i)
for(j=i-1; j>=i-7 && j>0; --j)
d=Minim(d, dist(aux[i],aux[j]) );
return d;
}
int main(){
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
printf("%.6lf\n",dist_min(1,n));
fclose(stdin); fclose(stdout);
return 0;
}