Cod sursa(job #2736604)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 3 aprilie 2021 17:42:57
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

using data = array<int, 2>;
using ll = long long;
ll sqr(ll x)
{
    return x * x;
}

struct KDtree
{
    int n, rez = 0;
    double best_dist;
    vector<data> pnct;

    KDtree(vector<data> pnct) : n(pnct.size()), pnct(pnct)
    {
        build(0, n, 0);
    }

    void build(int st, int dr, int tip)
    {
        if(dr <= st)
            return;
        int mij = (st + dr) / 2;
        nth_element(pnct.begin() + st, pnct.begin() + mij, pnct.begin() + dr, [&](data &a, data &b)
        {
            return a[tip] < b[tip];
        });
        build(st, mij, !tip);
        build(mij + 1, dr, !tip);
    }

    void work(int st, int dr, int tip, data p)
    {
        if(dr <= st)
            return;
        int mij = (st + dr) / 2;
        auto &q = pnct[mij];
        double dist =  sqrt(sqr(q[0] - p[0]) + sqr(q[1] - p[1]));
        if(dist != 0 && dist < best_dist)
            best_dist = dist;
        if(q[tip] - p[tip] > 0)
            work(st, mij, !tip, p);
        if(p[tip] - q[tip] > 0)
            work(mij + 1, dr, !tip, p);
    }
    double Aprop(data p)
    {
        best_dist = LLONG_MAX - 2;
        rez = 0;
        work(0, n, 0, p);
        return best_dist;
    }
};

int main()
{
    int n;
    fin >> n;
    vector<data> vec(n);
    for(int i = 0; i < n; ++i)
        fin >> vec[i][0] >> vec[i][1];

    KDtree Arb(vec);
    double minn = LLONG_MAX - 2;
    for(int i = 0; i < n; ++i)
        minn = min(minn, Arb.Aprop(vec[i]));
    fout << fixed << setprecision(6) << minn << '\n';
    return 0;
}