Cod sursa(job #2711887)

Utilizator KPP17Popescu Paul KPP17 Data 24 februarie 2021 20:32:09
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#define mF "cmap"
std::ifstream in(mF ".in");
std::ofstream out(mF ".out");
#include <complex>
#define x real
#define y imag
#define m (i+j>>1)
const int N = 100000;
struct P: public std::complex<double> {bool operator < (P p) {return x() == p.x()? y() < p.y(): x() < p.x();}} V[N], A[N];
double I(int i, int j)
{
    int l = i, p = i, q = m; while (p < m and q < j)
        if (V[p] < V[q]) A[l++] = V[p++]; else A[l++] = V[q++];
    while (p < m) A[l++] = V[p++]; while (q < j) A[l++] = V[q++];
    for (; i < j; i++) V[i] = A[i];
}
double R(int i, int j)
{
    switch (j - i) {case 1: return .8e9; case 2: return I(i, j), abs(V[i] - V[i+1]);}
    double r = R(i, m); r = std::min(r, R(m, j)); I(i, j);
    for (int p = i; p < j; p++) if (abs(V[p].y() - V[m].y()) < r)
        for (int q = p+1; q < p+8; q++) r = std::min(r, abs(V[p] - V[q]));
    return r;
}
#include <iomanip>
int main()
{
    int n; in >> n; for (int i = 0; i < n; i++) {int e; in >> e; V[i].x(e); in >> e; V[i].y(e);}
    out << std::fixed << std::setprecision(7) << R(0, n);
}