Cod sursa(job #3228689)

Utilizator TincaMateiTinca Matei TincaMatei Data 10 mai 2024 04:12:32
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.38 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 INFOARENA
    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::unordered_map<int, 
        std::unordered_map<int, std::vector<std::pair<int, int>>>> quad;

    long long min_dist_sqr = 1LL << 60;;
    int min_dist = (1 << 30) + 1;

    std::vector<std::pair<int, int> > points(n);

    for (int i = 0; i < n; i++) {
        std::cin >> points[i].first >> points[i].second;
        points[i].first += 1000000000;
        points[i].second += 1000000000;
    }

    std::mt19937 rng(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    std::shuffle(points.begin(), points.end(), rng);

    for (int i = 0; i < n; i++) {
        std::pair<int, int> p = points[i];

        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.first) == quad.end())
                    continue;

                if (quad[new_bucket.first].find(new_bucket.second) == quad[new_bucket.first].end())
                    continue;

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

        quad[bucket.first][bucket.second].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 (int j = 0; j <= i; j++) {
                std::pair<int, int> it = points[j];
                bucket = {it.first / min_dist, it.second / min_dist};
                quad[bucket.first][bucket.second].push_back(it);
            }
        }
    }

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

    return 0;
}