Cod sursa(job #1014235)

Utilizator Teodor94Teodor Plop Teodor94 Data 22 octombrie 2013 13:05:42
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.74 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

struct point {
    int x, y;
};

#define MAX_N 100000
#define INF 1000000000
#define EPS 0.0000001

point v[MAX_N], aux[MAX_N];

inline long long square( int x ) {
    return ( long long ) x * x;
}

inline double edist( point a, point b ) {
    return sqrt( square( a.x - b.x ) + square( a.y - b.y ) );
}

inline bool cmp( point a, point b ) {
    if ( a.x < b.x )
        return true;
    if ( a.x > b.x )
        return false;
    return ( a.y <= b.y );
}

void read( FILE *fin, int &n ) {
    fscanf( fin, "%d", &n );
    for ( int i = 0; i < n; ++i )
        fscanf( fin, "%d%d", &v[i].x, &v[i].y );
}

void merge( int left, int middle, int right ) {
    int i = left, j = middle + 1, pos = left - 1;
    while ( i <= middle && j <= right )
        if ( v[i].y <= v[j].y ) {
            aux[++pos] = v[i];
            ++i;
        } else {
            aux[++pos] = v[j];
            ++j;
        }
    while ( i <= middle ) {
        aux[++pos] = v[i];
        ++i;
    }
    while ( j <= right ) {
        aux[++pos] = v[j];
        ++j;
    }

    for ( i = left; i <= right; ++i )
        v[i] = aux[i];
}

double min_dist( int left, int right ) {
    // Daca intervalul nu are cel putin 2 elemente, returnez INF.
    if ( left >= right )
        return INF;
    // Daca am doua elemente, returnez distanta dintre ele.
    if ( left + 1 == right )
        return edist( v[left], v[right] );

    // Impart intervalul in doua, dupa dreapta verticala, avand coordonata punctului din mijloc.
    int middle = ( left + right ) >> 1, x_mid = v[middle].x;
    // Aflu distanta minima dintre doua puncte din stanga si din dreapta dreptei.
    double dist_left = min_dist( left, middle ), dist_right = min_dist( middle + 1, right );
    double dist = min( dist_left, dist_right );

    // Interclasez cele doua intervale de puncte, dupa a doua coordonata.
    merge( left, middle, right );

    // Caut punctele la distanta mai mica decat cea aflata de punctul din mijloc.
    int count = 0;
    for ( int i = left; i <= right; ++i )
        if ( abs( v[i].x - x_mid ) <= dist )
            aux[++count] = v[i];

    // Calculez distanta minima intre punctele determinate.
    double res = dist;
    for ( int i = 1; i <= count; ++i )
        for ( int j = i - 6; j >= 0 && j < i; ++j )
            res = min( res, edist( aux[i], aux[j] ) );

    return res;
}

int main() {
    FILE *fin, *fout;

    fin = fopen ( "cmap.in", "r" );
    int n;
    read( fin, n );
    fclose( fin );

    sort( v, v + n, cmp );

    fout = fopen( "cmap.out", "w" );
    fprintf( fout, "%lf\n", min_dist( 0, n - 1 ) );
    fclose( fout );
}