Cod sursa(job #2715893)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 4 martie 2021 12:57:23
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

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

const int NMAX = 1e5;

int N;
pair <int, int> v[NMAX + 5], aux[NMAX + 5];

double dist(pair<int, int> A, pair<int, int> B) {
    return sqrt((A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second));
}

double ABS(double x) {
    if(x < 0)
        return -x;

    return x;
}

double Solve(int st, int dr) {
    if(st == dr) {
        return 1e18;
    }

    int mid = (st + dr) >> 1;
    int pivotX = v[mid].first;

    double d1 = Solve(st, mid);
    double d2 = Solve(mid + 1, dr);

    double d = min(d1, d2);

    int p1 = st, p2 = mid + 1;
    int k = st - 1;

    while(k < dr) {
        k++;

        if(p1 > mid) {
            aux[k] = v[p2++];
        } else if(p2 > dr) {
            aux[k] = v[p1++];
        } else {
            if(v[p1].second < v[p2].second) {
                aux[k] = v[p1++];
            } else {
                aux[k] = v[p2++];
            }
        }
    }

    for(int i = st; i <= dr; i++) {
        v[i] = aux[i];
    }

    k = st - 1;
    for(int i = st; i <= dr; i++) {
        if(ABS(v[i].first - pivotX) <= d) {
            aux[++k] = v[i];
        }
    }

    for(int i = st; i <= k; i++) {
        for(int j = i + 1; j <= min(i + 8, k); j++) {
            d = min(d, dist(aux[i], aux[j]));
        }
    }

    return d;
}

int main() {
    cin >> N;

    for(int i = 1; i <= N; i++) {
        cin >> v[i].first >> v[i].second;
    }

    sort(v + 1, v + N + 1);

    cout << fixed << setprecision(6) << Solve(1, N) << '\n';

    return 0;
}