Cod sursa(job #2999765)

Utilizator DooMeDCristian Alexutan DooMeD Data 11 martie 2023 14:28:44
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
const int nmax = 1e5;

vector<pair<ll, ll>> v(nmax+5);

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

ll solve(int left, int right, vector<pair<ll, ll>>&x, vector<pair<ll, ll>>&y) {
    if(left >= right-1) return inf;
    if(right - left == 2) {
        if(y[left] > y[left+1]) swap(y[left], y[left+1]);
        return dist(x[left], x[left+1]);
    }
    int mid = (left + right) / 2;
    ll best = min(solve(left, mid, x, y), solve(mid, right, x, y));
    merge(y.begin() + left, y.begin() + mid, y.begin() + mid, y.begin() + right, v.begin());
    copy(v.begin(), v.begin() + (right - left), y.begin() + left);
    int temp = 0;
    for(int i=left; i<right; i++) 
        if(abs(y[i].second - x[mid].first) <= best)
            v[temp++] = y[i];
    for(int i=0; i<temp-1; i++)
        for(int j=i+1; j<temp and j-i < 8; j++)
            best = min(best, dist(v[i], v[j]));
    return best;
}

int main() {
    ifstream f("cmap.in");
    ofstream g("cmap.out");

    int n; f >> n;
    vector<pair<ll, ll>> x(n), y(n);
    for(int i=0; i<n; i++) f >> x[i].first >> x[i].second;
    sort(x.begin(), x.end());
    for(int i=0; i<n; i++) y[i] = {x[i].second, x[i].first};
    g << fixed << setprecision(6) << sqrt(solve(0, n, x, y));
    return 0;
}