Cod sursa(job #1120220)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 24 februarie 2014 22:16:23
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
#include <ctime>

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 v[Nmax], tmp[Nmax];
int N;

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

double DI( int st, int dr )
{
    int m = ( st + dr ) >> 1;

    if ( st >= dr ) return inf;

    if ( st + 1 == dr )
    {
        return distance( v[st], v[dr] );
    }

    double midPoint = v[m].x;
    double d1 = DI( st, m );
    double d2 = DI( m + 1, dr );
    double d = min( d1, d2 );

    int nr = 0;

    for ( int i = st; i <= dr; ++i )
    {
        if ( abs( v[i].x - midPoint ) <= d )
                tmp[ ++nr ] = v[i];
    }

    double min_dist = d;

    for ( int i = 1; i <= nr; ++i )
            for ( int j = i - 1; j >= i - 6 && j; --j )
                    min_dist = min( min_dist, distance( tmp[i], tmp[j] ) );

    return min_dist;
}

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

    srand( time( NULL ) );

    f >> N;

    for ( int i = 1; i <= N; ++i )
    {
        f >> v[i];
    }

    sort( v + 1, v + N + 1 );

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

    return 0;
}