Cod sursa(job #2952098)

Utilizator Fantastic_Mantudor voicu Fantastic_Man Data 8 decembrie 2022 11:42:40
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>

#define x first
#define y second

using namespace std;

const int nmax = 1e5;
const long long oo = 1e18;

pair < int, int > v[nmax + 1], rev[nmax + 1];
vector < pair < int, int > > srt;
pair < int, int > a[nmax + 1];

long long dist ( pair < int, int > a, pair < int, int > b ) {
    return ( long long ) ( a.x - b.x ) * ( a.x - b.x ) +
           ( long long ) ( a.y - b.y ) * ( a.y - b.y );
}

long long divide ( int st, int dr ) {
    if ( dr - st + 1 <= 3 ) {
        long long best = oo;
        for ( int i = st; i < dr; i++ )
            for ( int j = i + 1; j <= dr; j++ )
                best = min ( best, dist ( v[i], v[j] ) );
        sort ( rev + st, rev + dr );
        return best;
    }
    int mij = ( st + dr ) / 2;
    long long best = min ( divide ( st, mij ), divide ( mij + 1, dr ) );
    srt.resize ( dr - st + 1 );
    merge ( rev + st, rev + mij + 1,
            rev + mij + 1, rev + dr + 1,
            srt.begin () );

    for ( int i = 0; i < srt.size (); i++ )
        rev[i + st] = srt[i];

    int nr = 0;
    for ( int i = st; i <= dr; i++ )
        if ( ( long long ) ( rev[i].y - v[mij].x ) * ( rev[i].y - v[mij].x ) < best )
            a[nr++] = rev[i];

    for ( int i = 0; i < nr; i++)
        for ( int j = max ( 0, i - 7 ); j < i; j++)
            best = min ( best, dist ( a[i], a[j] ) );

    return best;
}



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

int main() {
    int n;
    fin >> n;
    for ( int i = 0; i < n; i++ )
        fin >> v[i].x >> v[i].y;
    sort ( v, v + n );
    for ( int i = 0; i < n; i++ )
        rev[i] = { v[i].second, v[i].first };

    fout << fixed << setprecision ( 6 ) << sqrt ( divide ( 0, n - 1 ) );

    return 0;
}