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