Cod sursa(job #2719351)

Utilizator KPP17Popescu Paul KPP17 Data 9 martie 2021 19:40:55
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#define mF "cmap"
std::ifstream in(mF ".in");
std::ofstream out(mF ".out");
#include <complex>
using P = std::complex<double>;
template<double (P::*x)() const, double (P::*y)() const>
constexpr bool comp(const P& a, const P& b)
{return (a.*x)() == (b.*x)()? (a.*y)() < (b.*y)(): (a.*x)() < (b.*x)();}
P V[100000];
#include <algorithm>
#define x real
#define y imag
#define m (i+j>>1)
double R(int i, int j)
{
    if (j - i == 1) return .5e10;
    double r = R(i, m), l = V[m].x(); r = std::min(r, R(m, j));
    std::inplace_merge(V + i, V + m, V + j, comp<&P::y, &P::x>);
    for (; i < j; i++) if (std::abs(V[i].x() - l) < r)
        for (int k = i+1; k < i+4 and k < j; k++)
            r = std::min(r, std::abs(V[i] - V[k]));
    return r;
}
#include <iomanip>
int main()
{
    int n; in >> n; for (int i = 0; i < n; i++) {double x, y; in >> x >> y; V[i].x(x); V[i].y(y);}
    std::sort(V, V + n, comp<&P::x, &P::y>); out << std::fixed << std::setprecision(6) << R(0, n);
}