Pagini recente » Cod sursa (job #831897) | Cod sursa (job #2202878) | Cod sursa (job #2779702) | Cod sursa (job #1062609) | Cod sursa (job #821973)
Cod sursa(job #821973)
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
int n, x, y;
vector<pair<int, int> > A;
inline double dis(const pair<int, int> & p1, const pair<int, int> & p2) {
double dx = p1.first - p2.first;
double dy = p1.second - p2.second;
return dx * dx + dy * dy;
}
double solve(int lo, int hi) {
double d = 1e20;
if (hi - lo <= 3) {
for (int i = lo; i < hi; i++) {
for (int j = i + 1; j < hi; j++) {
d = min(d, dis(A[i], A[j]));
}
}
} else {
int mid = (lo + hi) / 2;
d = min(solve(lo, mid), solve(mid, hi));
for (int i = mid - 1, c1 = 0; c1 < 8 && i >= lo; c1++, i--) {
for (int j = mid, c2 = 0; c2 < 8 && j < hi; c2++, j++) {
d = min(d, dis(A[i], A[j]));
}
}
}
return d;
}
int main() {
ifstream cin("cmap.in");
ofstream cout("cmap.out");
cin >> n;
A.reserve(n);
for (int i = 0; i < n; i++) {
cin >> x >> y;
A.push_back(make_pair(x, y));
}
sort(A.begin(), A.end());
cout << fixed << setprecision(6) << sqrt(solve(0, n));
return 0;
}