Pagini recente » Cod sursa (job #2867639) | Cod sursa (job #924147) | Cod sursa (job #910560) | Cod sursa (job #1766062) | Cod sursa (job #869141)
Cod sursa(job #869141)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int Nmax = 100010;
const double inf = 2e+9;
int n, m;
struct art {int x, y;} A[Nmax], aux[Nmax];
inline int cmpx(const art &A, const art &B)
{ if (A.x == B.x) return A.y < B.y;
return A.x < B.x;
}
inline int cmpy(const art &A, const art &B)
{ if (A.y == B.y) return A.x < B.x;
return A.y < B.y;
}
inline double sqr(double x) {return x * x;}
inline double dist(const art &A, const art &B)
{ return sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));}
double solve(int st, int dr)
{ if (st == dr) return inf;
if (st + 1 == dr) return dist(A[st], A[dr]);
int mid = (st + dr) / 2;
double d1 = solve(st, mid);
double d2 = solve(mid + 1, dr);
double ans = min(d1, d2);
m = 0;
for (int i = st; i <= dr; i++)
if ((A[i].x <= A[mid].x && A[i].x + ans >= A[mid].x) ||
(A[i].x >= A[mid].x && A[i].x - ans <= A[mid].x))
aux[++m] = A[i];
sort(aux + 1, aux + m + 1, cmpy);
int last = 1;
for (int i = 1; i <= m; i++)
{ while (aux[last].y + ans <= aux[i].y) last++;
for (int j = last; j < i; j++)
ans = min(ans, dist(aux[j], aux[i]));
}
return ans;
}
int main()
{ freopen("cmap.in", "r", stdin); freopen("cmap.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d %d", &A[i].x, &A[i].y);
sort(A + 1, A + n + 1, cmpx);
printf("%lf\n", solve(1, n));
return 0;
}