Cod sursa(job #403307)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 24 februarie 2010 20:28:39
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <algorithm>
#include <bitset>
#include <vector>
#include <math.h>
using namespace std;

#define DIM 405
#define INF 0x3f3f3f3f

int N;
int cnt, l[ DIM ], r[ DIM ];
float dst_max, dst_sort[ DIM*DIM ], x_sold[ DIM ], y_sold[ DIM ], dst[ DIM ][ DIM ];
bitset <DIM> f;
vector <int> v[ DIM ];

inline int pair_up( const int &nod ) {

    vector <int> :: iterator it;

    if( f[ nod ] )
        return 0;

    f[ nod ] = 1;
    for( it = v[ nod ].begin(); it != v[ nod ].end(); ++it )
        if( !r[ *it ] ) {

            l[ nod ] = *it;
            r[ *it ] = nod;

            return 1;
        }
    for( it = v[ nod ].begin(); it != v[ nod ].end(); ++it )
        if( pair_up( r[ *it ] ) ) {

            l[ nod ] = *it;
            r[ *it ] = nod;

            return 1;
        }

    return 0;
}

inline int cuplaj_max() {

    int i, ok, cuplaj;

    cuplaj = 0;
    memset( l, 0, sizeof( l ) );
    memset( r, 0, sizeof( r ) );

    do {

        ok = 0;
        f.reset();
        for( i = 1; i <= N; ++i )
            if( !l[ i ] && pair_up( i ) ) {

                ++cuplaj;
                ok = 1;
            }
    }
    while( ok );

    if( cuplaj == N )
        return 1;

    return 0;
}

int main() {

    freopen( "adapost.in", "r", stdin );
    freopen( "adapost.out", "w", stdout );

    int i, j, mid, left, right;
    float x_adap, y_adap, distanta;

    scanf( "%d", &N );
    for( i = 1; i <= N; ++i )
        scanf( "%f %f", &x_sold[ i ], &y_sold[ i ] );

    for( i = 1; i <= N; ++i ) {

        scanf( "%f %f", &x_adap, &y_adap );
        for( j = 1; j <= N; ++j ) {

            distanta = sqrt( ( x_sold[ j ] - x_adap ) * ( x_sold[ j ] - x_adap ) + ( y_sold[ j ] - y_adap ) * ( y_sold[ j ] - y_adap ) );
            dst_sort[ ++cnt ] = distanta;
            dst[ j ][ i ] = distanta;
        }
    }

    sort( dst_sort+1, dst_sort+cnt+1 );

    left = 1;
    right = cnt;
    while( left <= right ) {

        mid = (left+right) / 2;

        for( i = 1; i <= N; ++i )
            v[ i ].clear();
        for( i = 1; i <= N; ++i )
            for( j = 1; j <= N; ++j )
                if( dst[ i ][ j ] <= dst_sort[ mid ] )
                    v[ i ].push_back( j );

        if( cuplaj_max() ) {

            dst_max = dst_sort[ mid ];
            right = mid-1;
        }
        else
            left = mid+1;
    }

    printf( "%f", dst_max );

    return 0;
}