Pagini recente » Cod sursa (job #1851153) | infoarena - te ajutam sa devii olimpic! | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #1690352) | Cod sursa (job #3234089)
#include <bits/stdc++.h>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
using pii = pair<int, int>;
using ld = long double;
const ld inf = 1e9;
const int lim = 1e5 + 4;
pii v[lim];
int n;
bool bySecond(pii a, pii b) {
if (a.second == b.second) {
return a.first < b.first;
}
return a.second < b.second;
}
ld dist(pii a, pii b) {
return sqrt(1. * (a.first - b.first) * (a.first - b.first) +
1. * (a.second - b.second) * (a.second - b.second));
}
ld solve(int l, int r) {
if (l >= r) {
return inf;
}
int med = (l + r) >> 1;
int line = v[med].first;
ld d = min(solve(l, med), solve(med + 1, r));
vector<pii> manual;
for (int i = l; i <= r; ++i) {
if (v[i].first >= line - d and v[i].first <= line + d) {
manual.push_back(v[i]);
}
}
sort(manual.begin(), manual.end(), bySecond);
int lefty = 0;
ld ans = d;
for (int c = 0; c < manual.size(); ++c) {
pii p = manual[c];
while (manual[lefty].second < p.second - d) {
++lefty;
}
for (int i = lefty; i < c; ++i) {
ans = min(ans, dist(manual[i], p));
}
}
return ans;
}
int main() {
in >> n;
for (int i = 1; i <= n; ++i) {
in >> v[i].first >> v[i].second;
}
sort(v + 1, v + n + 1);
out << fixed << setprecision(9) << solve(1, n) << '\n';
return 0;
}