Cod sursa(job #1121088)

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

using namespace std;

const int Nmax = 100002;
const double inf = 1e18;
const double EPS = 1e-10;

struct Point
{
    double x, y;
    int ind;

    Point( double a = 0, double b = 0, int in = -1 )
    {
        x = a;
        y = b;
        ind = in;
    }
};

struct NOD
{
    int ind1, ind2;
    double dist;

    NOD( int in1 = -1, int in2 = -1, double dist1 = inf )
    {
        ind1 = in1;
        ind2 = in2;
        dist = dist1;
    }

    friend ostream& operator << ( ostream &f, NOD ND )
    {
        int a = min( ND.ind1, ND.ind2 );
        int b = max( ND.ind1, ND.ind2 );

        ///f << a << " " << b << " ";
        f << fixed << setprecision( 10 ) << ND.dist;
        return f;
    }
};

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

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

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

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

NOD DI( int st, int dr )
{
    if ( st == dr ) return NOD( -1, -1, inf );
    if ( st + 1 == dr ) return NOD( v[st].ind, v[dr].ind, DIST( v[st], v[dr] ) );

    int m = ( st + dr ) / 2;
    NOD d1 = DI( st, m );
    NOD d2 = DI( m + 1, dr );
    NOD d;

    if ( d1.dist > d2.dist )
            d = d2;
    else
            d = d1;

    int k = 0;

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

    sort( tmp, tmp + k, cmpy );

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

                if ( d.dist > ddd )
                {
                    d = NOD( v[ tmp[i] ].ind, v[ tmp[j] ].ind, ddd );
                }
            }

    return d;
}

int main()
{
    ifstream cin("cmap.in");
    ofstream cout("cmap.out");

    cin >> N;

    for ( int i = 0; i < N; ++i )
    {
        cin >> v[i].x >> v[i].y;
        v[i].ind = i;
    }

    sort( v, v + N, cmpx );

    cout << DI( 0, N - 1 ) << "\n";

    return 0;
}