Pagini recente » Cod sursa (job #2223196) | Cod sursa (job #2448444) | Cod sursa (job #1991214) | Cod sursa (job #1461768) | Cod sursa (job #1566991)
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct sp
{
long long x,y;
} ve[100005];
int si[100005],di[100005];
bool cmp(sp a1,sp a2)
{
if(a1.y!=a2.y)
return a1.y<a2.y;
return a1.x<a2.x;
}
bool cm2(sp a1,sp a2)
{
if(a1.x!=a2.x)
return a1.x<a2.x;
return a1.y<a2.y;
}
long long dist(int i,int j)
{
return (ve[i].x-ve[j].x)*(ve[i].x-ve[j].x)+(ve[i].y-ve[j].y)*(ve[i].y-ve[j].y);
}
long long solve(int st,int dr)
{
long long ans=-1,a2;
int i,j,mi=(st+dr)/2,ls=0,ld=0,l;
if(dr-st<=3)
{
for(i=st;i<=dr;i++)
for(j=i+1;j<=dr;j++)
if(dist(i,j)<ans || ans<0)
ans=dist(i,j);
return ans;
}
sort(ve+st,ve+dr+1,cmp);
ans=min(solve(st,mi),solve(mi+1,dr));
sort(ve+st,ve+dr+1,cm2);
for(i=st;i<=dr;i++)
if(ve[i].y<=ve[mi].y)
{
ls++;
si[ls]=i;
}
else
{
ld++;
di[ld]=i;
}
l=1;
a2=sqrt(ans);
for(i=1;i<=ls;i++)
for(j=l;j<=ld;j++)
{
if(ve[si[i]].x<ve[di[j]].x-a2)
break;
if(ve[si[i]].x>ve[di[j]].x+a2)
l=j+1;
ans=min(ans,dist(si[i],di[j]));
}
for(i=1;i<ls;i++)
ans=min(ans,dist(si[i],si[i+1]));
for(i=1;i<ld;i++)
ans=min(ans,dist(di[i],di[i+1]));
return ans;
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
int n,i,j;
long long ans;
double af;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lld%lld",&ve[i].x,&ve[i].y);
ans=solve(1,n);
af=sqrt(ans);
printf("%lf\n",af);
return 0;
}