Pagini recente » Cod sursa (job #2872887) | Cod sursa (job #3282922) | Cod sursa (job #1207202) | Cod sursa (job #3202145) | Cod sursa (job #407353)
Cod sursa(job #407353)
#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;
}