Pagini recente » Diferente pentru utilizator/florinhaja intre reviziile 159 si 43 | Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1008071)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cstdio>
using namespace std;
#define x first
#define y second
typedef long long llong;
typedef pair<llong,llong> Pair;
const int Nmax = 100010;
const llong oo = 1LL << 60;
int N;
Pair A[Nmax], B[Nmax],V[Nmax];
bool cmpx( Pair a, Pair b ){
if( a.x == b.x ) return a.y < b.y;
return a.x < b.x;
}
bool cmpy( Pair a, Pair b ){
if( a.y == b.y ) return a.x < b.x;
return a.y < b.y;
}
llong square( llong a ){
return a*a;
}
llong distance1( Pair& a, Pair& b ){
return square(a.x-b.x) + square(a.y-b.y);
}
void merge( int left, int mid, int right ){
int i = left, j = mid+1;
int k = 0;
while( i <= mid && j <= right ){
if( B[i].y < B[j].y ){
V[++k] = B[i++];
}
else{
V[++k] = B[j++];
//continue;
}
//V[++k] = B[i++];
//V[++k] = B[j++];
}
while( i <= mid ){
V[++k] = B[i++];
}
while( j <= right ){
V[++k] = B[j++];
}
for( int i = 1, j=left ; i<=k; i++, j++ )
B[j] = V[i];
}
llong go( int left, int right ){
//if( left >= right )
// return oo;
if( right - left < 2 ){
llong min1 = distance1( A[left], A[left+1] );
for( int i = left; i <= right; i++ )
for( int j = i+1; j <= right; j++ )
min1 = min( min1, distance1( A[i], A[j] ) );
sort( B+left, B+right+1, cmpy );
return min1;
}
int mid = (left+right)/2;
long long delta = min( go(left, mid), go(mid+1,right) );
merge( left, mid, right );
int k = 1;
for( int i = left; i <= right; i++ )
if( abs( B[i].x - A[mid].x ) <= delta ){
V[k] = B[i];
k++;
}
for( int i = 1; i < k ; i++ )
for( int j = i+1; j <= k && j-i < 8; j++ )
delta = min(delta, distance1( V[i], V[j] ) );
return delta;
}
int main(){
ifstream in("cmap.in");
ofstream out("cmap.out");
in >> N;
for( int i = 1; i <= N; i++ ){
in >> A[i].x >> A[i].y;
}
sort( A+1, A+N+1, cmpx );
for( int i = 1; i <= N; i++ )
B[i] = A[i];
llong rez = go( 1, N );
out<<fixed<<setprecision(6)<<sqrt(rez)<<endl;
return 0;
}