Cod sursa(job #3228683)

Utilizator TincaMateiTinca Matei TincaMatei Data 10 mai 2024 03:53:47
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <bits/stdc++.h>

long long sqr_dist(std::pair<int, int> a, std::pair<int, int> b) {
    return ((long long)(a.first - b.first) * (a.first - b.first) +
            (long long)(a.second - b.second) * (a.second - b.second));
}

int main() {
    std::cin.tie(NULL);
    std::iostream::sync_with_stdio(false);

#ifdef EVAL
    std::ifstream fin("cmap.in");
    std::ofstream fout("cmap.out");

    auto cinbuf = std::cin.rdbuf(fin.rdbuf());
    auto coutbuf = std::cout.rdbuf(fout.rdbuf());
#endif

    int n;
    std::cin >> n;

    std::map<std::pair<int, int>, std::vector<std::pair<int, int>>> quad;

    long long min_dist_sqr = 1LL << 60;;
    int min_dist = 1 << 30;

    std::vector<std::pair<int, int> > points;
    for (int i = 0; i < n; i++) {
        std::pair<int, int> p;
        std::cin >> p.first >> p.second;

        p.first  += 1000000000;
        p.second += 1000000000;

        std::pair<int, int> bucket = {p.first / min_dist, p.second / min_dist};
    
        for (int dl = -1; dl <= 1; dl++)
            for (int dc = -1; dc <= 1; dc++) {
                std::pair<int, int> new_bucket = {bucket.first + dl, bucket.second + dc};

                if (quad.find(new_bucket) == quad.end())
                    continue;

                for (auto it: quad[new_bucket])
                    min_dist_sqr = std::min(min_dist_sqr, sqr_dist(it, p));
            }

        quad[bucket].push_back(p);
        points.push_back(p);
        
        int new_min_dist = (int)std::round(std::sqrt(min_dist_sqr));

        if (new_min_dist < min_dist) {
            min_dist = new_min_dist;
            quad.clear();

            for (auto it: points) {
                bucket = {it.first / min_dist, it.second / min_dist};
                quad[bucket].push_back(it);
            }
        }
    }

    std::cout << std::fixed << std::setprecision(10) << std::sqrt(min_dist_sqr);

    return 0;
}