Pagini recente » Cod sursa (job #2901180) | Cod sursa (job #1169516) | Cod sursa (job #2497172) | Cod sursa (job #262614) | Cod sursa (job #1201142)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define MAX 100005
const long long INF = 1ll<<62;
struct punct
{
int x, y;
}v[MAX];
int y[MAX], aux[MAX];
bool cmp(punct a, punct b) {return a.x < b.x;}
long long solve(int st, int dr);
long long dist(punct a, punct b);
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
int n, i;
scanf("%d",&n);
for(i=1; i<=n; i++){
scanf("%d%d",&v[i].x,&v[i].y);
y[i]=i;
}
sort(v+1, v+n+1, cmp);
printf("%lf\n",sqrt((double)solve(1,n)));
return 0;
}
long long solve(int st, int dr)
{
int mij, i, j, k;
long long ds, dd, d;
if(st+1 == dr)
{
if(v[st].y > v[dr].y)
{
y[st]=dr; y[dr]=st;
}
return dist(v[st],v[dr]);
}
if(st==dr) return INF;
mij = (dr+st)/2;
d = solve(st, mij);
dd = solve(mij+1, dr);
if(d > dd) d=dd;
i=st; j=mij+1;
k=0;
while(i <= mij and j <= dr)
{
if(v[y[i]].y <= v[y[j]].y)
aux[++k] = y[i++];
else
aux[++k] = y[j++];
}
while(i<=mij) aux[++k] = y[i++];
while(j<=dr) aux[++k] = y[j++];
for(i=st; i<=dr; i++)
y[i] = aux[i-st+1];
for(i=st; i<=dr; i++)
if(abs(v[mij].x-v[y[i]].x) <= d)
aux[++k] = y[i];
for(i=1; i<k; i++)
for(j=1; j<8 && i+j<=k; j++)
{
dd = dist(v[aux[i]], v[aux[i+j]]);
if(!dd) dd=INF;
if(d>dd) d = dd;
}
return d;
}
long long dist(punct a, punct b)
{
return 1ll*(a.x-b.x)*(a.x-b.x) + 1ll*(a.y-b.y)*(a.y-b.y);
}