Cod sursa(job #2867175)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 10 martie 2022 11:26:18
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define NMAX 100005
const long long INF =  4e18;
int n;
vector<pair<long long, long long>> x, y, v(NMAX);
long long dist(pair<long long, long long> A, pair<long long, long long> B)
{
    return (A.first - B.first) * (A.first - B.first)
           +   (A.second - B.second) * (A.second - B.second);
}
long long solve(int st, int dr, vector<pair<long long, long long>> &X, vector<pair<long long,long long>> &Y)
{
    if (st >= dr - 1) {
        return INF;
    }
    else if (dr - st == 2){
        if (Y[st] > Y[st+1])
            swap(Y[st], Y[st+1]);

        return dist(X[st], X[st+1]);
    }
    int mij = (st + dr) / 2;
    long long best = min(solve(st, mij, X, Y), solve(mij, dr, X, Y));

    merge(Y.begin() + st, Y.begin()+mij, Y.begin()+mij, Y.begin()+dr, v.begin());
    copy(v.begin(), v.begin()+(dr-st), Y.begin()+st);

    int vlen = 0;
    for (int i=st;i<dr;i++){
        if (abs(Y[i].second - X[mij].first) <= best)
            v[vlen ++] = Y[i];
    }

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

    return best;
}
int main() {
    fin >> n;
    x.resize(n);
    y.resize(n);
    for (int i=0;i<n;i++){
        fin >> 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};
    }

    fout << fixed << setprecision(6) << sqrt(solve(0, n, x, y)) << '\n';

    return 0;
}