Cod sursa(job #2567385)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 3 martie 2020 16:57:44
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

#define llg     long long
#define ldb     long double

int N;
std::vector <std::pair <int, int>> V;
std::set    <std::pair <int, int>> set;

llg dist2(int x0, int y0, int x1, int y1) {
    llg ans = 1ll*(x0-x1)*(x0-x1) + 1ll*(y0-y1)*(y0-y1);
    return ans;
}

#define FILENAME    std::string("cmap")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

int32_t main()
{
    input >> N;
    V.resize(N);
    for (auto &it:V) input >> it.first >> it.second;
    std::sort(V.begin(), V.end());

    int ptr = 0;
    llg min = 4e18;
    for (int i=0; i<V.size(); ++i) {
        while ((V[i].first - V[ptr].first)*(V[i].first - V[ptr].first) > min)
            set.erase({V[ptr].second, V[ptr].first}), ++ ptr;

        auto it1 = set.lower_bound({V[i].second-ceil(sqrt(min)), V[i].first});
        auto it2 = set.upper_bound({V[i].second+ceil(sqrt(min)), V[i].first});

        for (; it1!=it2; ++it1)
            min = std::min(min, dist2(it1->second, it1->first, V[i].first, V[i].second));
        set.insert({V[i].second, V[i].first});
    }   output << std::fixed << std::setprecision(6) << sqrt((ldb)(min)) << '\n';

    return 0;
}