Pagini recente » Cod sursa (job #1091437) | Cod sursa (job #3258116) | Cod sursa (job #230482) | Cod sursa (job #3291672) | Cod sursa (job #407337)
Cod sursa(job #407337)
#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;
}