Pagini recente » Cod sursa (job #2675466) | Cod sursa (job #617670) | Cod sursa (job #772913) | Cod sursa (job #1310464) | Cod sursa (job #1712891)
#include <cstdio>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair<int,int> punct;
typedef long long ll;
const ll inf=10e18;
punct v[100010],aux[100010];
int cmp(punct a,punct b)
{
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
ll dist(punct a,punct b)
{
return 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
}
ll solve(int st,int dr)
{
if(st>=dr) return inf;
else if(st+1==dr)
{
if(cmp(v[dr],v[st])) swap(v[st],v[dr]);
return dist(v[st],v[dr]);
}
int mid=(st+dr)/2,midx=v[mid].x,nr=0;
ll sol=min(solve(st,mid),solve(mid+1,dr));
merge(v+st,v+mid+1,v+mid+1,v+dr+1,aux+1,cmp);
for(int i=1;i<=dr-st+1;i++) v[st+i-1]=aux[i];
for(int i=1;i<=dr-st+1;i++)
if(1LL*abs(aux[i].x-midx)*abs(aux[i].x-midx)<=sol) aux[++nr]=aux[i];
for(int i=1;i<=nr;i++)
for(int j=i+1;j<=nr && 1LL*(aux[j].y-aux[i].y)*(aux[j].y-aux[i].y)<=sol;j++) sol=min(sol,dist(aux[i],aux[j]));
return sol;
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i].x,&v[i].y);
sort(v+1,v+1+n);
printf("%f",sqrt(solve(1,n)));
return 0;
}