Pagini recente » Cod sursa (job #2102013) | Cod sursa (job #1940654) | Cod sursa (job #1184535) | Cod sursa (job #1059970) | Cod sursa (job #1198680)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define MAX 100001
const long long INF = 1ll<<62;
struct punct{
int x, y;
} p[MAX];
int y[MAX], n, 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){return 1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y);}
int main()
{
int i;
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d%d", &p[i].x, &p[i].y);
y[i] = i;
}
sort(p+1, p+n+1, cmp);
printf("%f", sqrt((double)solve(1, n)));
return 0;
}
long long solve(int st, int dr)
{
int i, j, k;
long long d, dd;
if(st+1==dr){
if(p[st].y>p[dr].y) y[st] = dr, y[dr] = st;
return dist(p[st], p[dr]);
}
if(st==dr) return INF;
int mij = (st+dr)/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 && j<=dr)
if(p[y[i]].y<p[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+1-st];
for(i=st; i<dr; i++)
for(j=1; j<8 && i+j<=dr; j++){
dd = dist(p[i], p[i+j]);
if(d>dd) d = dd;
}
return d;
}