Pagini recente » Cod sursa (job #2356440) | Cod sursa (job #977986) | Cod sursa (job #1896306) | Cod sursa (job #1592201) | Cod sursa (job #2284243)
#include <iostream>
#include <queue>
#include <cmath>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define f first
#define s second
#define ll long long
using namespace std;
pair<ll,ll> v[100010];
ll n,i,j ,m,ans;
double dist( pair<ll,ll> a, pair<ll,ll> b ){
return sqrt( (a.f-b.f)*(a.f-b.f) + (a.s-b.s)*(a.s-b.s) );
}
bool cmp( pair<ll,ll> a, pair<ll,ll> b ){
if( a.s > b.s ) return true;
else if( a.s < b.s ) return false;
if( a.f >= b.f ) return true;
return false;
}
long double cmapip( ll left, ll right ){
ll middle = ( left + right ) / 2;
double ans = 2000000000;
if( right - left <= 3 ){
for( ll i = left ; i <= right ; i++ ){
for( ll j = i + 1 ; j <= right ; j++ ){
ans = min( ans , dist( v[ i ] , v[ j ] ) );
}
}
return ans;
}
ans = min( cmapip( left , middle ) , cmapip( middle + 1 , right ) );
vector< pair<ll,ll> > vec;
for( int i = left ; i <= right ; i++ ){
if( abs( v[ i ].f - v[ middle ].f ) <= ans ){
vec.push_back( v[ i ] );
}
}
int l = vec.size();
sort(vec.begin(), vec.end(), [](auto &left, auto &right) {
return left.second < right.second;
});
for( int i = 0 ; i < l ; i++ ){
for( int j = i + 1 ; j < min( l , i + 8 ) ; j++ ){
ans = min( ans , dist( vec[ i ] , vec[ j ] ) );
}
}
return ans;
}
int main(){
ifstream cin("cmap.in");
ofstream cout("cmap.out");
cin >> n;
for( ll i = 1 ; i <= n ; i++ ){
cin >> v[ i ].f >> v[ i ].s;
}
sort( v + 1 , v + n + 1 );
cout << fixed << setprecision(7) << cmapip( 1 , n );
return 0;
}