Cod sursa(job #407353)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 2 martie 2010 11:35:28
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

#define INF 1LL<<60
#define MAX_N 100005

typedef int int_32;
typedef long long int int_64;

int_32 N;
int_64 XXX;
vector < pair <int_64, int_64> > p, aux;

struct cmp {

    bool operator()( const pair <int_64, int_64> &a, const pair <int_64, int_64> &b ) {

        return a.second < b.second;
    }
};

int_64 dst( const pair <int_64, int_64> &a, const pair <int_64, int_64> &b ) {

    return ( a.first - b.first ) * ( a.first - b.first ) + ( a.second - b.second ) * ( a.second - b.second );
}

void go( const int_32 &left, const int_32 &right ) {

    int_32 mid;
    vector < pair <int_64, int_64> > :: iterator it_1, it_2;

    if( right - left <= 2 ) {

        for( it_1 = p.begin() + left; it_1 != p.begin() + right - 1; ++it_1 )
            for( it_2 = it_1 + 1; it_2 != p.begin() + right; ++it_2 )
                XXX = min( XXX, dst( *it_1, *it_2 ) );

        return;
    }

    mid = ( left + right ) / 2;

    go( left, mid );
    go( mid+1, right );

    aux.clear();
    for( it_1 = p.begin() + left; it_1 != p.begin() + right; ++it_1 )
        if( abs( it_1->second - p[ mid ].second ) <= XXX )
            aux.push_back( *it_1 );

    sort( aux.begin(), aux.end(), cmp() );

    for( it_1 = aux.begin(); it_1 != aux.end() - 1; ++it_1 )
        for( it_2 = it_1 + 1; it_2 != aux.end() && it_2 - it_1 < 8; ++it_2 )
            XXX = min( XXX, dst( *it_1, *it_2 ) );
}

int main() {

    freopen( "cmap.in", "r", stdin );
    freopen( "cmap.out", "w", stdout );

    int i;

    scanf( "%d", &N );

    p.resize( N );
    for( i = 0; i < N; ++i ) {

        scanf( "%lld", &p[ i ].first );
        scanf( "%lld", &p[ i ].second );
    }

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

    XXX = INF;
    go( 0, N-1 );

    printf( "%lf", sqrt( XXX ) );

    return 0;
}