Pagini recente » Cod sursa (job #2475277) | Cod sursa (job #1964995) | Cod sursa (job #3273815) | Cod sursa (job #296236) | Cod sursa (job #472662)
Cod sursa(job #472662)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf (double)(0x7fffffff*sqrt(2))
struct punct
{
int x,y;
} v[100005],y[100005];
int n,i;
struct cmp
{
inline bool operator()(const punct &a,const punct &b)const
{
return a.x<b.x;
}
};
struct cmpy
{
inline bool operator()(const punct &a,const punct &b)const
{
return a.y<b.y;
}
};
inline double dist(punct a,punct b)
{
return sqrt(1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y));
}
inline int minim(int a,int b)
{
if (a<b)
return a;
return b;
}
double sol(int st,int dr)
{
int i,j,mid,a,b,c,x,nr1,nr2;
double aux,ret,s1,s2;
if (st>dr)
return inf;
if (dr-st+1<=3)
{
ret=inf;
for (i=st;i<dr;++i)
for (j=i+1;j<=dr;++j)
{
aux=dist(v[i],v[j]);
if (aux<ret)
ret=aux;
}
return ret;
}
mid=st+((dr-st)>>1);
x=v[mid].x;
s1=sol(st,mid);
s2=sol(mid+1,dr);
if (s2<s1)
s1=s2;
a=st;
b=mid;
while (a<=b)
{
c=a+((b-a)>>1);
if (x-v[c].x>=s1)
a=c+1;
else
b=c-1;
}
nr1=b+1;
a=mid+1;
b=dr;
while (a<=b)
{
c=a+((b-a)>>1);
if (v[c].x-x>=s1)
b=c-1;
else
a=c+1;
}
nr2=b;
for (i=nr1;i<=nr2;++i)
y[i-nr1+1]=v[i];
sort(y+1,y+nr2-nr1+2,cmpy());
ret=inf;
for (i=1;i<=nr2-nr1+1;++i)
for (j=i+1;j<=minim(i+7,nr2-nr1+1);++j)
{
aux=dist(y[i],y[j]);
if (aux<ret)
ret=aux;
}
if (s1<ret)
return s1;
return ret;
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;++i)
scanf("%d %d",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp());
printf("%.6lf",sol(1,n));
return 0;
}