Pagini recente » Clasament solares | Cod sursa (job #227731) | Cod sursa (job #2204840) | Cod sursa (job #583206) | Cod sursa (job #2284196)
#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) );
}
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() );
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;
}