Cod sursa(job #2604008)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 21 aprilie 2020 14:34:23
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
#define PLEC fin.close(); fout.close(); return 0;
#define x    first
#define y    second
using namespace std;
const string problem("cmap");
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");
typedef long long i64;
using PII = pair<i64, i64>;
vector<PII> v;
set<PII> s;
int n;
i64 ys, yd, j(1);
double res(1e18);
inline double Dist(PII a, PII b) {
    return sqrt(1.0 * ((1LL * (a.x - b.x) * (a.x - b.x)) + (1LL * (a.y - b.y) * (a.y - b.y))));
}
int main() {
    DAU
    fin >> n;
    v = vector<PII>(n + 1);
    for (int i = 1; i <= n; ++i)
        fin >> v[i].x >> v[i].y;
    sort(v.begin() + 1, v.end());
    for (int i = 1; i <= n; ++i) {
        while (!s.empty() && (v[i].x - v[j].x) >= res)
            s.erase(s.find({v[j].y, v[j].x})), ++j;
        ys = v[i].y - static_cast<i64>(res) - 1;
        yd = v[i].y + static_cast<i64>(res) + 1;
        auto st = s.lower_bound({ys, 1e9});
        auto dr = s.lower_bound({yd, 1e9});
        for (auto it = st; it != dr; ++it) {
            if (it == s.end())
                break;
            res = min(res, Dist(v[i], {it -> second, it -> first}));
        }
        s.emplace(v[i].y, v[i].x);
    }
    fout << fixed << setprecision(10) << res;
    PLEC
}