Pagini recente » Cod sursa (job #2146653) | Cod sursa (job #1830442) | Cod sursa (job #1226947) | Cod sursa (job #2738968) | Cod sursa (job #590525)
Cod sursa(job #590525)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define INF 4e18
using namespace std;
int n,i,j,vs;
struct punct{long long x; long long y;};
punct x[100001],y[100001],v[100001];
int cmp(punct a,punct b)
{
if (a.x!=b.x)
return (a.x<b.x);
return (a.y<b.y);
}
inline void swap(punct &a,punct &b)
{
punct aux=a;
a=b;
b=aux;
}
long long dist(punct x,punct y)
{
return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}
inline long long min(long long a,long long b)
{
if (a>b) return b;
return a;
}
long long apel(int st,int dr)
{
if (st>=dr-1) return INF;
if (dr-st==2)
{
if (y[st].x>y[st+1].x || (y[st].x==y[st+1].x && y[st].y>y[st+1].y))
swap(y[st],y[st+1]);
return dist(x[st],x[st+1]);
}
int m=(st+dr)/2;
long long best=min(apel(st,m),apel(m,dr));
sort(y+st+1,y+dr+1,cmp);
vs=0;
for (i=st;i<dr;i++)
if (abs(y[i].y-x[m].x)<=best)
v[++vs]=y[i];
for (i=1;i<=vs;i++)
{
for (j=i+1;j<=vs && j-i<=7;j++)
best=min(best,dist(v[i],v[j]));
}
return best;
}
int main(void)
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%lld%lld",&x[i].x,&x[i].y);
sort(x+1,x+n+1,cmp);
for (i=1;i<=n;i++)
{
y[i].x=x[i].y;
y[i].y=x[i].x;
}
printf("%.6llf",sqrt(apel(1,n+1)));
return 0;
}