Pagini recente » Cod sursa (job #3253306) | Cod sursa (job #2872460) | Cod sursa (job #228592) | Cod sursa (job #3282923) | Cod sursa (job #410954)
Cod sursa(job #410954)
#include <stdio.h>
#include <math.h>
double sol;
long n,i,x[100100],y[100100],v[100100],a[100100],b[100100];
double dist(long i,long j)
{double dx,dy;
dx=x[i]-x[j];
dy=y[i]-y[j];
return sqrt((dx)*(dx)+(dy)*(dy));
}
int cmp(long i,long j)
{if(x[i]<x[j]||(x[i]==x[j]&&y[i]<y[j]))return 1;
return 0;
}
void merge_sort(long st,long dr)
{long mij=st+((dr-st)>>1),i,j,k;
if(st!=dr)
{merge_sort(st,mij);
merge_sort(mij+1,dr);
for(i=st,j=mij+1,k=st;i<=mij||j<=dr;)
if(j>dr||(i<=mij&&cmp(i,j)))
{a[k++]=x[i++];b[k-1]=y[i-1];}
else
{a[k++]=x[j++];b[k-1]=y[j-1];}
for(k=st;k<=dr;k++){x[k]=a[k];y[k]=b[k];}
}
}
double cmap(long st,long dr)
{double dmin=2000000000,dd;
long i,j;
if(dr-st<3)
{for(i=st;i<dr;i++)
for(j=i+1;j<=dr;j++)
{dd=dist(i,j);
if(dd<dmin)dmin=dd;
if(y[i]>y[j])
{x[0]=x[i];x[i]=x[j];x[j]=x[0];y[0]=y[i];y[i]=y[j];y[j]=y[0];}
}
return dmin;
}
long mij,xx,k=st,xxx;
double s1,s2;
mij=st+((dr-st)>>1);
xx=x[mij];
s1=cmap(st,mij);
s2=cmap(mij+1,dr);
if(s2<s1)s1=s2;
for(i=st,j=mij+1;i<=mij||j<=dr;)
if((j>dr)||(i<=mij&&y[i]<=y[j])){a[k++]=x[i++];b[k-1]=y[i-1];}
else {a[k++]=x[j++];b[k-1]=y[j-1];}
k=0;
for(i=st;i<=dr;i++)
{x[i]=a[i];y[i]=b[i];
xxx=x[i]-xx;
if(xxx<0)xxx=-xxx;
if(xxx<=s1){k++;v[k]=i;}
}
for(i=1;i<k;i++)
for(j=i+1;j<=k&&j<=i+7;j++)
{dd=dist(v[i],v[j]);
if(dd<dmin)dmin=dd;
}
if(dmin>s1)dmin=s1;
return dmin;
}
int main()
{freopen("cmap.in","r",stdin);freopen("cmap.out","w",stdout);
scanf("%ld",&n);
for(i=1;i<=n;i++)scanf("%ld%ld",&x[i],&y[i]);
merge_sort(1,n);
n=n;
sol=cmap(1,n);
printf("%lf",sol);
fclose(stdin);fclose(stdout);
return 0;
}