Mai intai trebuie sa te autentifici.
Cod sursa(job #2736591)
Utilizator | Data | 3 aprilie 2021 17:34:26 | |
---|---|---|---|
Problema | Cele mai apropiate puncte din plan | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.73 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(p[tip] - q[tip] > 0)
work(st, mij, !tip, p);
if(sqr(p[tip] - q[tip]) >= best_dist)
return;
if(q[tip] - p[tip] > 0)
work(mij + 1, dr, !tip, p);
}
double Aprop(data p)
{
best_dist = (1 << 30);
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 = (1 << 30);
for(int i = 0; i < n; ++i)
minn = min(minn, Arb.Aprop(vec[i]));
fout << fixed << setprecision(6) << minn << '\n';
return 0;
}