Cod sursa(job #1466894)

Utilizator petru.cehanCehan Petru petru.cehan Data 31 iulie 2015 15:30:58
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

ifstream fin ("cmap.in") ;
ofstream fout ("cmap.out") ;

typedef long long LL ;

const int MAX_N = 100005 ;
const LL INF = 4e18 ;

vector < pair < LL , LL > > V(MAX_N) , X , Y ;

LL dist ( const pair < LL , LL >& a , const pair < LL , LL >& b )
{
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second) ;
}

LL closest ( int st , int dr , vector < pair < LL , LL> >& X , vector < pair < LL , LL > >& Y )
{
    if ( st >= dr - 1 ) // cazurile pentru 1 pct sau 2 pcte
        return INF;
    else if (dr - st == 2) // cazul pt 3 puncte..cel de baza
    {
        if ( Y[st] > Y[st + 1] ) // sortez crescator dupa ordonata
            swap ( Y[st] , Y[st + 1] ) ;
        return dist ( X[st], X[st + 1] ) ;
    }

    int mid = (st + dr) / 2;
    LL best = min ( closest ( st , mid , X , Y ) , closest ( mid , dr , X , Y ) ) ;

    merge ( Y.begin() + st, Y.begin() + mid , Y.begin() + mid , Y.begin() + dr , V.begin() ) ; // interclasez in vectorul rezultat V , cele 2 jumatati
    copy ( V.begin() , V.begin() + ( dr - st ) , Y.begin() + st ) ;
    // sau cele 2 ( merge , copy ) < = > cu o simpla sortare    sort(Y.begin() + st, Y.begin() + dr);

    int v_size = 0 ;
    for ( int i = st ; i < dr ; ++ i)
      if ( abs ( Y[i].second - X[mid].first ) <= best )
            V[ v_size ++ ] = Y[i] ;
    for ( int i = 0 ; i < v_size - 1 ; ++ i)
    {
        for ( int j = i + 1 ; j < v_size && j - i < 8 ; ++ j )
            best = min ( best , dist( V[i] , V[j] ) ) ;
    }
    return best ;
}

int main()
{
    int n;
    fin >> n ;

    X.resize(n) , Y.resize(n) ;
    for (int i = 0; i < (int) X.size(); ++ i )
        fin >> X [i].first >> X [i].second ;

    sort ( X.begin(), X.end() ) ; // sorteaza implicit dupa primul camp ( first , adica dupa absisa )

    for ( int i = 0; i < (int) X.size(); ++ i )
        Y[i] = make_pair ( X[i].second , X[i].first ) ;

    fout << fixed << setprecision(6) << sqrt ( closest (0, (int) X.size(), X, Y ) ) << "\n";
    return 0;
}