Pagini recente » Cod sursa (job #370801) | Cod sursa (job #2204994) | Cod sursa (job #1499489) | Cod sursa (job #2081616) | Cod sursa (job #1007895)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cstdio>
using namespace std;
ifstream F("cmap.in");
ofstream G("cmap.out");
#define x first
#define y second
typedef pair<long long,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( cmpy(B[i],B[j]) ){
V[k] = B[i];
k++; i++;
continue;
}
if( cmpy(B[j],B[i]) ){
V[k] = B[j];
k++;j++;
continue;
}
V[k++] = B[i++];
V[k++] = B[j++];
}
while( i <= mid ){
V[k] = B[i];
k++; i++;
}
while( j <= right ){
V[k] = B[j];
k++;j++;
}
for( int i = left, t=0 ; t<k; t++,i++ )
B[i] = V[t];
}
long long go( int left, int right ){
if( left >= right )
return 1LL<<60;
if( right - left == 1 ){
if( !cmpy(B[left], B[right]) )
swap( B[left], B[right] );
return distance( A[left], A[right] );
}
int mid = (left+right)/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(){
F >> N;
for( int i = 0; i < N; i++ ){
F>> 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 );
G<<fixed<<setprecision(6)<<sqrt(go(1,N))<<"\n";
return 0;
}