Cod sursa(job #2871150)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 12 martie 2022 21:56:06
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits>
#include <iomanip>
#include <cmath>

#define MOD 666013
#define INT_MAX 1000000000

using namespace std ;

ifstream cin ("cmap.in") ;
ofstream cout ("cmap") ;

struct pct
{
    long double x, y ;
};

long double d(pct a, pct b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) ;
}

pct v[120009] ;

long double merg(int st, int dr)
{
    if(dr - st == 1)
        return d(v[st], v[dr]) ;

    if(st == dr)
        return (long double)INT_MAX * 3 ;

    int mid = (st + dr) / 2 ;

    long double mn = min(merg(st, mid), merg(mid + 1, dr)) ;

    /// consideram doar punctele care pe axa x

    long double l = (v[mid + 1].x + v[mid].x) / 2 ;

    vector<pct> X, Y ;

    for(int f = st ; f <= mid ; f ++)
        if(l - v[f].x + v[mid + 1].x - l < mn)X.push_back(v[f]) ;

    for(int f = mid + 1 ; f <= dr ; f ++)
        if(v[f].x - l + l - v[mid].x < mn)Y.push_back(v[f]) ;

    ///sort(X.begin(), X.end(), ord2) ; /// sorteaza dupa y
    ///sort(Y.begin(), Y.end(), ord2) ;

    for(int f = 0 ; f < X.size() ; f ++)
        for(int e = 0 ; e < Y.size() ; e ++)
            mn = min(mn, d(X[f], Y[e])) ;

    return mn ;
}

bool ord(pct a, pct b)
{
    return a.x < b.x ;
}

int main()
{
    int n ;

    cin >> n ;

    for(int f = 1 ; f <= n ; f ++)
        cin >> v[f].x >> v[f].y ;

    sort(v + 1, v + n + 1, ord) ;

    cout << fixed << setprecision(6) << merg(1, n) ;

    return 0 ;
}
/// 1990