Cod sursa(job #2926745)

Utilizator NuSuntRomanIspir Alexandru NuSuntRoman Data 18 octombrie 2022 16:48:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
/// Ispir Alexandru - O(n log^2 n)

#include <bits/stdc++.h>

const int NMAX = 2e5 + 5;

struct punct {
    long double x, y;
};

int n;
std :: vector < punct > p(NMAX);

std :: ifstream fin("cmap.in");
std :: ofstream fout("cmap.out");

bool cmpX(punct a, punct b) {
    if (a.x != b.x)
        return (a.x < b.x);

    return (a.y < b.y);
}

bool cmpY(punct a, punct b) {
    if (a.y != b.y)
        return (a.y < b.y);

    return (a.x < b.x);
}

long double dist(punct a, punct b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

long double solve(int l, int r) {
    if (r - l + 1 <= 3) {
        long double Min = 9e18;

        for (int i = l; i <= r; ++ i)
            for (int j = i + 1; j <= r; ++ j)
                Min = std :: min(Min, dist(p[i], p[j]));

        return Min;
    }
    else {
        int mid = ((l + r) >> 1);

        long double Min = std :: min(solve(l, mid), solve(mid + 1, r));

        std :: vector < punct > b;

        for (int i = l; i <= r; ++ i)
            if (abs(p[i].x - p[mid].x) <= Min)
                b.push_back(p[i]);

        std :: sort(b.begin(), b.end(), cmpY);

        for (int i = 0; i < b.size(); ++ i)
            for (int j = i + 1; j < std :: min(int(b.size()), i + 9); ++ j)
                Min = std :: min(Min, dist(b[i], b[j]));

        return Min;
    }
}

int main() {
    fin >> n;

    for (int i = 0; i < n; ++ i)
        fin >> p[i].x >> p[i].y;

    std :: sort(p.begin(), p.begin() + n, cmpX);

    fout << std :: fixed << std :: setprecision(8) << solve(0, n - 1);

    return 0;
}