Pagini recente » Cod sursa (job #2040199) | Romanii medaliati la IOI | Cod sursa (job #2137211) | Istoria paginii runda/jkn/clasament | Cod sursa (job #1466894)
#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;
}