Pagini recente » Cod sursa (job #2496408) | Cod sursa (job #252195) | Cod sursa (job #2386140) | Cod sursa (job #1224870) | Cod sursa (job #3139170)
#include <bits/stdc++.h>
using namespace std;
double dist(pair<double, double> a, pair<double, double> b) {
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
double closestPairDistance(vector<pair<double, double>> &x, vector<pair<double, double>> &y, int p, int q) {
if (p >= q) {
return 4e18;
} else if (q - p == 1) {
if (y[p] > y[q]) swap(y[p], y[q]);
return dist(x[p], x[q]);
}
int mid = (p + q) / 2;
double best = min(closestPairDistance(x, y, p, mid - 1), closestPairDistance(x, y, mid, q));
sort(y.begin() + p, y.begin() + q + 1);
vector<pair<double, double>> v(q - p + 1);
int v_size = 0;
for (int i = p; i <= q; ++i) {
if (abs(y[i].second - x[mid].first) <= best) v[v_size++] = y[i];
}
for (int i = 0; i < v_size - 1; ++i) {
for (int j = i + 1; j < v_size && j - i < 8; ++ j) {
best = min(best, dist(v[i], v[j]));
}
}
return best;
}
int main() {
ifstream cin("cmap.in");
ofstream cout("cmap.out");
int n; cin >> n;
vector<pair<double, double>> x(n);
vector<pair<double, double>> y(n);
for (int i = 0; i < n; ++i) {
cin >> x[i].first >> x[i].second;
}
sort(x.begin(), x.end());
for (int i = 0; i < n; ++ i) {
y[i] = make_pair(x[i].second, x[i].first);
}
cout << setprecision(18) << sqrt(closestPairDistance(x, y, 0, n - 1));
return 0;
}