Cod sursa(job #3139170)

Utilizator AndreiPaval03Andrei Paval AndreiPaval03 Data 25 iunie 2023 19:28:35
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

double dist(pair<double, double> a, pair<double, double> b) {
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

double closestPairDistance(vector<pair<double, double>> &x, vector<pair<double, double>> &y, int p, int q) {
    if (p >= q) {
        return 4e18;
    } else if (q - p == 1) { 
        if (y[p] > y[q]) swap(y[p], y[q]);
        return dist(x[p], x[q]);
    }

    int mid = (p + q) / 2;
    double best = min(closestPairDistance(x, y, p, mid - 1), closestPairDistance(x, y, mid, q));

    sort(y.begin() + p, y.begin() + q + 1);

    vector<pair<double, double>> v(q - p + 1);
    int v_size = 0;
    for (int i = p; i <= q; ++i) {
        if (abs(y[i].second - x[mid].first) <= best) v[v_size++] = y[i];
    }
    for (int i = 0; i < v_size - 1; ++i) {
        for (int j = i + 1; j < v_size && j - i < 8; ++ j) {
            best = min(best, dist(v[i], v[j]));
        }
    }
    return best;

}

int main() {
    ifstream cin("cmap.in");
    ofstream cout("cmap.out");

    int n; cin >> n;
    vector<pair<double, double>> x(n);
    vector<pair<double, double>> y(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i].first >> x[i].second;
    }

    sort(x.begin(), x.end());
    for (int i = 0; i < n; ++ i) {
        y[i] = make_pair(x[i].second, x[i].first);
    }

    cout << setprecision(18) << sqrt(closestPairDistance(x, y, 0, n - 1));

    return 0;
}