Cod sursa(job #2710205)

Utilizator As932Stanciu Andreea As932 Data 22 februarie 2021 09:57:36
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#define ll long long
#define per pair<ll,ll>

using namespace std;

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

const ll inf = 4e18;
const int nmx = 1e5 + 5;

int n;
vector <per> x, y, v(nmx);

void read(){
    cin >> n;

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

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

ll solve(int l, int r){
    if(l >= r - 1)
        return inf;
    else if(r - l == 2){
        if(y[l] > y[l + 1])
            swap(y[l], y[l + 1]);
        return dist(x[l], x[l + 1]);
    }

    int mid = (l + r) / 2;
    ll best = min(solve(l, mid), solve(mid, r));

    merge(y.begin() + l, y.begin() + mid, y.begin() + mid, y.begin() + r, v.begin());
    copy(v.begin(), v.begin() + (r - l), y.begin() + l);

    int sz = 0;
    for(int i = l; i < r; i++)
        if(abs(y[i].second - x[mid].first) <= best)
            v[sz++] = y[i];

    for(int i = 0; i < sz - 1; i++)
        for(int j = i + 1; j < sz && j - i < 8; j++)
            best = min(best, dist(v[i], v[j]));

    return best;
}

int main()
{
    read();
    sort(x.begin(), x.end());

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

    cout << fixed << setprecision(6) << sqrt(solve(0, n)) << "\n";

    return 0;
}