Cod sursa(job #2284194)

Utilizator DysKodeTurturica Razvan DysKode Data 16 noiembrie 2018 22:30:49
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <queue>
#include <cmath>
#include <fstream>
#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 <= 2 ){
    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 ) );
  deque< ll > dq;
  ll ans1 = ans;
  for( ll i = left ; i <= right ; i++ ){
    if( abs( v[ i ].f - v[ middle ].f ) <= ans1 ){
      for( ll j = 0 ; j < dq.size() ; j++ ){
        ans = min( ans , dist( v[ i ] , v[ dq[ j ] ] ) );
      }
      dq.push_back( i );
      if( dq.size() == 8 ) dq.pop_back();
    }
  }
  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;
}