Cod sursa(job #1120376)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 24 februarie 2014 23:32:02
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;

const int Nmax = 100002;
const double inf = 1e18;

struct Point
{
    double x, y;

    Point( const double _x = 0, const double _y = 0 )
    {
        x = _x;
        y = _y;
    }

    bool operator < ( const Point P ) const
    {
        if ( x != P.x )
                return x < P.x;
        else
                return y < P.y;
    }

    friend istream& operator >> ( istream &f, Point &P )
    {
        f >> P.x >> P.y;
        return f;
    }
};

Point X[Nmax], Y[Nmax], aux[Nmax];
int N;

double DIST( Point A, Point B )
{
    return ( pow( A.x - B.x, 2.0 ) + pow( A.y - B.y, 2.0 ) );
}

double DI( int st, int dr )
{
    if ( st >= dr - 1 ) return inf;

    if ( st + 2 == dr )
    {
        sort( Y + st, Y + dr );

        return DIST( X[st], X[st + 1] );
    }

    double d;
    int m = ( st + dr ) / 2;

    d = min( DI( st, m ), DI( m, dr ) );

    merge( Y + st, Y + m, Y + m, Y + dr, aux );
    copy( aux, aux + dr - st, Y + st );

    int nr = 0;

    for ( int i = st; i < dr; ++i )
            if ( abs( Y[i].y - X[m].x ) <= d )
                    aux[ ++nr ] = Y[i];

    double min_dist = inf;

    for ( int i = 1; i <= nr; ++i )
            for ( int j = i + 1; j <= nr && j - i < 8; ++j )
                    min_dist = min( min_dist, DIST( aux[i], aux[j] ) );

    return min_dist;
}

int main()
{
    ifstream f("cmap.in");
    ofstream g("cmap.out");

    f >> N;

    for ( int i = 0; i < N; ++i )
    {
        f >> X[i];

        Y[i] = Point( X[i].y, X[i].x );
    }

    g << fixed << setprecision( 10 );
    g << sqrt( DI( 0, N ) ) << endl;

    return 0;
}