Pagini recente » Cod sursa (job #1977392) | Cod sursa (job #1977456) | Cod sursa (job #1149787) | Cod sursa (job #1442716) | Cod sursa (job #2736584)
#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;
work(st, mij, !tip, p);
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;
}