Pagini recente » Cod sursa (job #2108981) | Cod sursa (job #1837480) | Cod sursa (job #2943044) | Cod sursa (job #2214618) | Cod sursa (job #1389628)
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define fi first
#define se second
using namespace std;
const int NMAX = 100004;
pair < int ,int > v[NMAX], a[NMAX], aux[NMAX];
inline long long sqr(const long long x)
{
return 1LL*x*x;
}
inline long long Dist(const pair < int ,int > A,const pair < int ,int > B)
{
return sqr(A.fi-B.fi)+sqr(A.se-B.se);
}
inline long long Solve(const int Left,const int Right)
{
if(Left >= Right)
return 1LL<<60;
if(Left == Right-1)
{
sort(a+Left,a+Right+1);
return Dist(a[Left],a[Right]);
}
int mid = (Left+Right)/2;
long long Sol = min(Solve(Left,mid),Solve(mid+1,Right));
merge(a+Left,a+mid+1,a+mid+1,a+Right+1,aux);
copy(aux,aux+Right-Left+1,a+Left);
int k = 0;
for(int i=Left;i<=Right;++i)
if(sqr(a[i].se-v[mid].fi) <= Sol)
aux[++k] = a[i];
for(int i = 1;i <= k;++i)
for(int j=i+1;j <= k && j-i <= 8; ++j)
Sol = min(Sol,Dist(aux[i],aux[j]));
return Sol;
}
int main()
{
int n, x, y;
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d\n",&n);
for(int i=1;i<=n;++i)
{
scanf("%d %d\n",&x,&y);
v[i] = make_pair(x,y);
}
sort(v+1,v+n+1);
for(int i=1;i<=n;++i)
a[i] = make_pair(v[i].se,v[i].fi);
long double D = sqrt(Solve(1,n));
cout<<setprecision(7)<<fixed;
cout<<D<<"\n";
return 0;
}