Cod sursa(job #2663510)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 26 octombrie 2020 17:07:57
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>
#define se second
#define fi first
#define ll long long
#define pll pair<long long,long long>
#define mp make_pair
using namespace std;

ifstream f ( "cmap.in" );
ofstream g ( "cmap.out" );
const int MAX_N = 100005;
const ll INF = 4e18;

vector < pll> V ( MAX_N ), X, Y;

ll dist ( const pll& a, const pll& b )
{
    return ( a.fi - b.fi ) * ( a.fi - b.fi ) + ( a.se - b.se ) * ( a.se - b.se );
}
ll go ( int st, int dr, vector <pll >& X, vector < pll >& 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 mid = ( st + dr ) / 2;
    ll best = min ( go ( st, mid, X, Y ), go ( mid, dr, X, Y ) );
    merge ( Y.begin() + st, Y.begin() + mid, Y.begin() + mid, Y.begin() + dr, V.begin() );/// se face intreclasarea elem din Ps si celor din Pd
    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;
    f >> n;
    X.resize ( n ), Y.resize ( n );

    for ( int i = 0; i < n; ++ i )
        f >> X[i].fi >> X[i].se;

    sort ( X.begin(), X.end() );

    for ( int i = 0; i < n; ++ i )
        Y[i] = mp ( X[i].se, X[i].fi );

    g << fixed << setprecision ( 6 ) << sqrt ( go ( 0, X.size(), X, Y ) ) << "\n";
    return 0;
}