Cod sursa(job #2763837)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 17 iulie 2021 09:06:32
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;

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

const int NMAX = 1e5;

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

long double ABS(long double d) {
    return max(d, -d);
}

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

long double Solve(int st, int dr) {
    if(st >= dr) {
        return 1e15;
    }

    int mid = (st + dr) >> 1;
    long double d1 = Solve(st, mid);
    long double d2 = Solve(mid + 1, dr);
    long double d = min(d1, d2);

    int k = st, p1 = st, p2 = mid + 1;
    while(p1 <= mid || p2 <= dr) {
        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[mid].first - v[i].first) <= d) {
            aux[++k]= v[i];
        }
    }

    for(int i = st; i <= k; i++) {
        for(int j = max(st, i - 7); j < i; 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(8) << Solve(1, N) << '\n';
    return 0;
}