Cod sursa(job #2414409)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 24 aprilie 2019 16:02:13
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>

#define NMAX 100000
#define x first
#define y second
#define pint pair<int, int>

using namespace std;

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

pint v[1 + NMAX], p[1 + NMAX];

double minim ( double a, double b ) {
    return ( a < b ) ? a : b;
}

double dist ( pint a, pint b ) {
    return sqrt ( ( double ) ( a.x - b.x ) * ( a.x - b.x ) + ( double ) ( a.y - b.y ) * ( a.y - b.y ) );
}

double cmp ( pint a, pint b ) {
    return a.y < b.y;
}

double sol ( int st, int dr ) {

    if ( dr - st + 1 <= 3 ) {
        sort ( v + st, v + dr + 1, cmp );

        double ans = INFINITY;

        for ( int i = st; i <= dr; ++ i )
            for ( int j = i + 1; j <= dr; ++ j )
                ans = minim ( ans, dist ( v[i], v[j] ) );

        return ans;
    }

    int mid = ( st + dr ) / 2;
    int xmid = v[mid].x;

    double ans = minim ( sol ( st, mid ), sol ( mid + 1, dr ) );

    int ind = st;
    int i = st, j = mid + 1;

    while ( i <= mid && j <= dr ) {
        if ( v[i].y < v[j].y )
            p[ind ++] = v[i ++];
        else
            p[ind ++] = v[j ++];
    }

    for ( ; i <= mid; ++ i ) p[ind ++] = v[i];

    for ( ; j <= dr; ++ j ) p[ind ++] = v[j];

    for ( int i = st; i <= dr; ++ i )
        v[i] = p[i];

    ind = 0;

    for ( int i = st; i <= dr; ++ i )
        if ( fabs ( v[i].x - xmid ) < ans )
            p[ind++] = v[i];

    for ( int i = 0; i < ind; ++ i )
        for ( int j = i + 1; j <= i + 7 && j < ind; ++ j )
            ans = min ( ans, dist ( p[i], p[j] ) );

    return ans;

}

int main() {

    int N;

    fin >> N;

    for ( int i = 1; i <= N; ++i )
        fin >> v[i].x >> v[i].y;

    fout << setprecision(8) << fixed;

    sort( v + 1, v + N + 1 );
    fout << sol (1, N);

    return 0;
}