Pagini recente » Cod sursa (job #2388777) | Cod sursa (job #2943294) | Cod sursa (job #614462) | Cod sursa (job #2229823) | Cod sursa (job #559389)
Cod sursa(job #559389)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define pii pair <int,int>
#define x first
#define y second
#define NMAX 100005
#define inf 1LL<<62
using namespace std;
pii a[NMAX];
int n,b[NMAX],r;
inline long long d(int x,int y)
{
return (long long)(a[x].x-a[y].x)*(a[x].x-a[y].x)+(long long)(a[x].y-a[y].y)*(a[x].y-a[y].y);
}
inline long long min(long long x,long long y)
{
return x<y ? x : y;
}
long long solve(long long st,long long dr)
{
if (st==dr)
return inf;
if (dr-st==1)
return d(st,dr);
int mij=(st+dr)/2;
long long rez=min(solve(st,mij),solve(mij+1,dr));
r=0;
int i,j;
for (i=st; i<=mij; i++)
if (a[mij].x-a[i].x<=rez)
b[++r]=i;
for (i=mij+1; i<=dr; i++)
if (a[i].x-a[mij].x<=rez)
b[++r]=i;
for (i=1; i<=r; i++)
for (j=i+1; j<=r && j-i<8; j++)
rez=min(rez,d(b[i],b[j]));
return rez;
}
int main()
{
long long rez;
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d",&n);
int i;
for (i=1; i<=n; i++)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+n+1);
rez=solve(1,n);
printf("%.7lf\n",sqrt((double)rez));
return 0;
}