Cod sursa(job #2713749)

Utilizator KPP17Popescu Paul KPP17 Data 28 februarie 2021 15:42:58
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#define mF "cmap"
std::ifstream in(mF ".in");
std::ofstream out(mF ".out");
const int N = 100000;
#include <complex>
#define x real
#define y imag
struct P: std::complex<double>
{inline bool operator < (P p) {return x() == p.x()? y() < p.y(): x() < p.x();}} V[N], O[N];
#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));
    int p = i, q = m, k = i; while (p < m and q < j)
        O[k++] = V[p].y() < V[q].y()? V[p++]: V[q++];
    while (p < m) O[k++] = V[p++]; while (q < j) O[k++] = V[q++];
    for (p = i; p < j; p++) if (V[p] = O[p], abs(O[p].x() - l) < r)
        for (q = p+1; q < p+7 and q < j; q++) r = std::min(r, abs(O[p] - O[q]));
    return r;
}
#undef m
#include <algorithm>
#include <iomanip>
int main()
{
    int n; in >> n; for (int i = 0; i < n; i++) {int a, b; in >> a >> b; V[i].x(a), V[i].y(b);}
    std::sort(V, V + n); out << std::fixed << std::setprecision(7) << R(0, n);
}