Cod sursa(job #2890695)

Utilizator tiut_cristianTiut Cristian tiut_cristian Data 16 aprilie 2022 12:39:36
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
vector <pair<i64,i64>> V(100001), X, Y;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

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

i64 rez(int st, int dr, vector<pair<i64,i64>> & X, vector<pair<i64,i64>> & Y)
{
    if (st >= dr - 1)
        return 4e18;
    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 mid = (st + dr) / 2;
    i64 best = min(rez(st, mid, X, Y), rez(mid, dr, X, Y));

    merge(Y.begin()+st, Y.begin()+mid, Y.begin()+mid, Y.begin()+dr, V.begin());
    copy(V.begin(), V.begin()+dr-st, Y.begin() + st);

    int v_size = 0;
    for (int i = st; i < dr; i++)
        if (abs(Y[i].second - X[mid].first) <= best)
            V[v_size++] = Y[i];
    for (int i = 0; i < v_size - 1; i++)
        for (int j = i + 1; j < v_size && j-i < 8; j++)
            best = min(best, dist(V[i], V[j]));
    return best;
}

int main()
{
    int n;
    fin >> n;

    X.resize(n);
    Y.resize(n);

    for (int i = 0; i < (int) X.size(); i++)
        fin >> X[i].first >> X[i].second;
    sort(X.begin(), X.end());

    for (int i = 0; i < (int) X.size(); i++)
        Y[i] = {X[i].second, X[i].first};

    fout << fixed << setprecision(6) << sqrt(rez(0, (int) X.size(), X, Y)) << '\n';

    return 0;
}