Cod sursa(job #1243685)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 16 octombrie 2014 10:44:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

class ClosestPair
{
public:

    ClosestPair(const vector< pair<int,int> >& a)
    {
        Points.resize( a.size() );
        tmp.resize( a.size() );

        for ( int i = 0; i < a.size(); ++i )
            Points[i] = a[i];

        sort( Points.begin(), Points.end() );
    }

    double solve()
    {
        return sqrt( rec( 0, Points.size() - 1 ) );
    }

private:

    vector < pair<int,int> > Points, tmp;

    i64 distance( const pair<int,int>& a, const pair<int,int>& b ) const
    {
        return 1LL * ( a.first - b.first ) * ( a.first - b.first ) +
               1LL * ( a.second - b.second ) * ( a.second - b.second );
    }

    i64 rec( int st, int dr )
    {
        if ( st >= dr )
            return 1e18;

        if ( st + 1 == dr )
        {
            if ( Points[st].second > Points[dr].second )
                swap( Points[st], Points[dr] );

            return distance( Points[st], Points[dr] );
        }
        else
        {
            int m = ( st + dr ) / 2;
            int mid = Points[m].first;
            i64 d1 = rec( st, m );
            i64 d2 = rec( m + 1, dr );
            i64 d = min( d1, d2 );

            int i = st, j = m + 1, k = st;

            while ( i <= m && j <= dr )
            {
                if ( Points[i].second <= Points[j].second )
                    tmp[ k++ ] = Points[ i++ ];
                else
                    tmp[ k++ ] = Points[ j++ ];
            }

            while ( i <= m ) tmp[ k++ ] = Points[ i++ ];
            while ( j <= dr ) tmp[ k++ ] = Points[ j++ ];

            for ( int i = st; i <= dr; ++i )
                Points[i] = tmp[i];

            int nr = 0;

            for ( int i = st; i <= dr; ++i )
            {
                if ( abs( Points[i].first - mid ) <= d )
                    tmp[ nr++ ] = Points[i];
            }

            for ( int i = 0; i < nr; ++i )
                for ( int j = i - 1, k = 8; j >= 0 && k > 0; j--, k-- )
                    d = min( d, distance( tmp[i], tmp[j] ) );

            return d;
        }
    }
};

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

    vector < pair<int,int> > a;
    int N;

    f >> N;

    for ( int i = 1; i <= N; ++i )
    {
        pair<int,int> x;
        f >> x.first >> x.second;
        a.push_back( x );
    }

    ClosestPair P( a );

    g << fixed << setprecision( 10 );
    g << P.solve() << endl;

    return 0;
}