Pagini recente » Cod sursa (job #22402) | Cod sursa (job #746243) | Cod sursa (job #124606) | Cod sursa (job #2459625) | Cod sursa (job #986336)
Cod sursa(job #986336)
#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 long long square_distance (const point &a, const point &b) {
return (b.x - a.x) * 1LL * (b.x - a.x) + (b.y - a.y) * 1LL * (b.y - a.y);
}
long long divide (const int &l, const int &r) {
if (l + 1 == r) {
if (_P[l] > _P[r])
swap (_P[l], _P[r]);
return square_distance (P[l], P[r]);
}
if (l == r)
return INF;
int m = l + r >> 1, i, N = 0;
long long p, q = min (divide (l, m), divide (m + 1, r));
double k = sqrt (q);
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) < k) {
N = i++;
break;
}
for (; i <= r; ++i)
if (fabs (_P[i].y - P[m].x) < k) {
p = square_distance (_P[N], _P[i]);
if (p < q)
q = p;
N = i;
}
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", sqrt (divide (1, N)));
}