Pagini recente » Cod sursa (job #1988028) | Cod sursa (job #2529933) | Cod sursa (job #2431790) | Cod sursa (job #1687672) | Cod sursa (job #984226)
Cod sursa(job #984226)
#include <cstdio>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair <int, int> point;
const long long INF = 2e18;
const int NMAX = 100003;
point P[NMAX], _P[NMAX], K[NMAX];
inline double dist (const point &a, const point &b) {
return sqrt ((b.x - a.x) * 1LL * (b.x - a.x) + (b.y - a.y) * 1LL * (b.y - a.y));
}
double divide (const int &l, const int &r) {
if (l + 1 == r) {
if (_P[l] > _P[r])
swap (_P[l], _P[r]);
return dist (P[l], P[r]);
}
if (l == r)
return INF;
int m = l + r >> 1, i, N = 0;
double p, q = min (divide (l, m), divide (m + 1, r));
merge (_P + l, _P + m + 1, _P + m + 1, _P + r + 1, K + 1);
copy (K + 1, K + (r - l + 2), _P + l);
for (i = l; i <= r; ++i)
if (fabs (_P[i].y - P[m].x) < q)
K[++N] = _P[i];
for (i = 2; i <= N; ++i) {
p = dist (K[i], K[i - 1]);
if (p < q)
q = p;
}
return q;
}
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", &P[i].x, &P[i].y);
sort (P + 1, P + N + 1);
for (i = 1; i <= N; ++i)
_P[i] = make_pair (P[i].y, P[i].x);
printf ("%.6lf", divide (1, N));
}