Pagini recente » Cod sursa (job #3252181) | Cod sursa (job #1749859) | Cod sursa (job #229896) | Cod sursa (job #670779) | Cod sursa (job #797417)
Cod sursa(job #797417)
#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;
int n,m,p1,p2,p;
pii A[NMAX],B[NMAX],C[NMAX],D[NMAX];
ll rez;
void read()
{
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);
}
inline ll min(ll x,ll y)
{
return x<y ? x : y;
}
inline ll d(pii a,pii b)
{
return (ll)(a.x-b.x)*(a.x-b.x)+(ll)(a.y-b.y)*(a.y-b.y);
}
ll search(int st,int dr)
{
if (st==dr)
{
C[st]=A[st];
return INF;
}
if (dr-st==1)
{
if (A[st].y<A[dr].y)
C[st]=A[st],C[st+1]=A[dr];
else
C[st]=A[dr],C[st+1]=A[st];
return d(A[st],A[dr]);
}
int mij=(st+dr)/2;
ll val=min(search(st,mij),search(mij+1,dr));
p1=st; p2=mij+1; p=st;
while (p1<=mij && p2<=dr)
{
if (C[p1].y<C[p2].y)
D[p]=C[p1],p1++,p++;
else
D[p]=C[p2],p2++,p++;
}
while (p1<=mij)
D[p]=C[p1],p1++,p++;
while (p2<=dr)
D[p]=C[p2],p2++,p++;
for (p=st; p<=dr; p++)
C[p]=D[p];
int i,j;
m=0;
for (i=st; i<=dr; i++)
if ((ll)(C[i].x-A[mij].x)*(C[i].x-A[mij].x)<=val)
B[++m]=C[i];
for (i=1; i<=m; i++)
for (j=i+1; j-i<8 && j<=m; j++)
val=min(val,d(B[i],B[j]));
return val;
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
read();
rez=search(1,n);
printf("%.7lf\n",sqrt((double)rez));
return 0;
}