Pagini recente » Cod sursa (job #1161790) | Cod sursa (job #1913062) | Cod sursa (job #1518681) | Cod sursa (job #1687202) | Cod sursa (job #1007871)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
#define x first
#define y second
typedef pair<long,long> Pair;
const int Nmax = 100010;
int N;
Pair A[Nmax], B[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;
}
long long distance( Pair a, Pair b ){
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
void merge( int left, int mid, int right ){
int i = left, j = mid+1;
int k = 0;
Pair V[Nmax];
while( i <= mid && j <= right ){
if( B[i].y < B[j]. y ){
V[k] = B[i];
k++; i++;
}
else{
V[k] = B[j];
k++;j++;
}
}
while( i <= mid ){
V[k] = B[i];
k++; i++;
}
while( j <= right ){
V[k] = B[j];
k++;j++;
}
int t = 0;
for( int i = left ; i <= right; i++ )
B[i] = V[t++];
}
long long go( int left, int right ){
if( right - left < 2 ){
if( B[left].y > B[left+1].y )
swap( B[left], B[left+1] );
return distance( A[left], A[left+1] );
}
int mid = left + (right-left)/2;
long long delta = min( go(left, mid), go(mid+1,right) );
merge( left, mid, right );
int k = 0;
Pair V[Nmax];
for( int i = left; i <= right; i++ )
if( abs( B[i].x - A[mid].x ) <= delta )
V[k++] = B[i];
for( int i = left; i <= right; i++ )
for( int j = i+1; j <= right && j-i < 8; j++ )
delta = min(delta, distance( B[i], B[j] ) );
return delta;
}
int main(){
freopen("cmap.in", "r", stdin );
freopen("cmpa.out", "w", stdout );
scanf("%d", &N );
for( int i = 0; i < N; i++ )
scanf("%d%d", &A[i].x, &A[i].y );
sort( A, A+N, cmpx );
for( int i = 0; i < N; i++ )
B[i] = A[i];
long long rez = go( 0, N-1 );
printf("%.6lf\n", sqrt( rez ) );
return 0;
}