Pagini recente » Cod sursa (job #507816) | Cod sursa (job #1081034) | Cod sursa (job #1528121) | Cod sursa (job #2703650) | Cod sursa (job #1567008)
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
pair<ll ,ll> ve[100005];
int si[100005],di[100005];
bool cmp(pair<ll,ll> a1,pair<ll,ll> a2)
{
return a1.first<a2.first;
}
long long dist(int i,int j)
{
return (ve[i].first-ve[j].first)*(ve[i].first-ve[j].first)+(ve[i].second-ve[j].second)*(ve[i].second-ve[j].second);
}
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);
for(i=st;i<=dr;i++)
if(ve[i].second<=ve[mi].second)
{
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]].first<ve[di[j]].first-a2)
break;
if(ve[si[i]].first>ve[di[j]].first+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].first,&ve[i].second);
ans=solve(1,n);
af=sqrt(ans);
printf("%lf\n",af);
return 0;
}