Cod sursa(job #2284243)

Utilizator DysKodeTurturica Razvan DysKode Data 17 noiembrie 2018 01:27:54
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#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;
}