Cod sursa(job #407337)

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

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

typedef int int_32;
typedef long long int int_64;

char s[ MAX_S ];
int_32 N;
int_32 cnt_s;
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 ) );
}

void read( int_32 &val ) {

    while( !isdigit( s[ cnt_s ] ) )
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }

    val = 0;
    while( isdigit( s[ cnt_s ] ) ) {

        val = val*10 + s[ cnt_s ] - '0';
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }
    }
}

void read( int_64 &val ) {

    while( !isdigit( s[ cnt_s ] ) )
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }

    val = 0;
    while( isdigit( s[ cnt_s ] ) ) {

        val = val*10 + s[ cnt_s ] - '0';
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }
    }
}

int main() {

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

    int i;

    cnt_s = MAX_S - 1;

    read( N );

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

        read( p[ i ].first );
        read( p[ i ].second );
    }

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

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

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

    return 0;
}