Pagini recente » Cod sursa (job #3124670) | Cod sursa (job #289724) | Cod sursa (job #661836) | Cod sursa (job #5570) | Cod sursa (job #1026774)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
using namespace std;
const int MaxArraySize = 100001;
const int Inf = 1 << 30;
int n;
double ans;
pair<int, int> vec[MaxArraySize], x[MaxArraySize], y[MaxArraySize];
double dist(pair<int, int> a, pair<int, int> b) {
return sqrt(1LL * (a.first - b.first) * (a.first - b.first) + 1LL * (a.second - b.second) * (a.second - b.second));
}
int modul(int val) {
if (val < 0)
return -val;
return val;
}
double dive_et_imp(int st, int dr) {
if (st >= dr - 1)
return Inf;
if (dr - st == 2)
return dist(x[st], x[st + 1]);
int mij, i, j, m = -1;
double sol;
mij = st + (dr - st) / 2;
sol = min(dive_et_imp(st, mij), dive_et_imp(mij, dr));
sort(y + st, y + dr);
for (i = st; i < dr; ++i)
if (sol >= modul(y[i].second - x[mij].first))
vec[++m] = y[i];
for (i = 0; i < m - 1; ++i) {
for (j = i + 1; j < m && j - i < 8; ++j)
sol = min(sol, dist(vec[i], vec[j]));
}
return sol;
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
int i;
scanf("%d", &n);
for (i = 0; i < n; ++i)
scanf("%d %d", &x[i].first, &x[i].second);
sort(x, x + n);
for (i = 0; i < n; ++i)
y[i] = make_pair(x[i].second, x[i].first);
ans = dive_et_imp(0, n);
printf("%lf", ans);
return 0;
}