Pagini recente » Istoria paginii utilizator/laviniasuciu | Cod sursa (job #1717612) | Cod sursa (job #1896828) | Cod sursa (job #5065) | Cod sursa (job #2680246)
#include <bits/stdc++.h>
using namespace std;
tuple<long long, Point, Point> ClosestPair(vector<Point> v) {
assert((int)v.size() > 1);
sort(v.begin(), v.end(), [&](Point a, Point b) {
return a.imag() < b.imag();
});
set<Point> s; int j = 0;
tuple<long long, Point, Point> ret{4e18, {}, {}};
for (auto p : v) {
long long d = 1 + sqrt(get<0>(ret));
while (v[j].imag() <= p.imag() - d) s.erase(v[j++]);
auto lo = s.lower_bound(p - d),
hi = s.upper_bound(p + d);
for (auto it = lo; it != hi; ++it)
ret = min(ret, {norm(*it - p), *it, p});
s.insert(p);
}
return ret;
}
int main() {
ifstream cin("cmap.in");
ofstream cout("cmap.out");
int n; cin >> n;
vector<Point> v(n);
for (int i = 0; i < n; ++i) {
double a, b; cin >> a >> b;
v[i] = {a, b};
}
auto d = get<0>(ClosestPair(v));
cout << fixed << setprecision(20) << sqrt(d) << endl;
return 0;
}