Cod sursa(job #1121010)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 25 februarie 2014 11:05:26
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

const int Nmax = 100005;
const double inf = 1e18;
const double EPS = 1e-12;

struct Point
{
    double x, y;

    Point( const double a = 0, const double b = 0 )
    {
        x = a;
        y = b;
    }

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

    friend ostream& operator << ( ostream &f, Point P )
    {
        f << P.x << " " << P.y;
        return f;
    }
};

Point v[Nmax];
int tmp[Nmax];
int N;

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

bool cmpy( int A, int B )
{
    return v[A].y < v[B].y;
}

bool cmpx( Point A, Point B )
{
    return A.x < B.x;
}

double DI( int st, int dr )
{
    if ( st == dr ) return inf;
    if ( st + 1 == dr ) return DIST( v[st], v[dr] );

    int m = ( st + dr ) / 2;
    double d1 = DI( st, m );
    double d2 = DI( m + 1, dr );
    double d = min( d1, d2 );
    int k = 0;

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

    sort( tmp, tmp + k, cmpy );

    double sol = d;

    for ( int i = 0; i < k; ++i )
    {
        for ( int j = i + 1; j < k && v[ tmp[j] ].y - v[ tmp[i] ].y < d; ++j )
        {
            double dist = DIST( v[ tmp[j] ], v[ tmp[i] ] );

            d = min( d, dist );
        }
    }

    return d;
}

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

    f >> N;

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

    sort( v, v + N, cmpx );

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

    return 0;
}