Cod sursa(job #2284179)

Utilizator DysKodeTurturica Razvan DysKode Data 16 noiembrie 2018 22:14:51
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <cmath>

#define f first
#define s second
#define ll long long

using namespace std;

pair<ll,ll> v[100010];
ll n,i,j ,m,ans;

ll dist( pair<ll,ll> a, pair<ll,ll> b ){
  return( (a.f-b.f)*(a.f-b.f) + (a.s-b.s)*(a.s-b.s) );
}

ll cmapip( ll left, ll right ){
  ll middle = ( left + right ) / 2;
  ll 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;
  for( ll i = left ; i <= right ; i++ ){
    if( abs( v[ i ].f - v[ middle ].f ) <= ans ){
      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 fin("cmap.in");
  ofstream fout("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 << setprecission(7) << sqrt( cmapip( 1 , n ) );

return 0;
}