Pagini recente » Cod sursa (job #2939855) | Cod sursa (job #2718973) | Cod sursa (job #617685) | Cod sursa (job #967231) | Cod sursa (job #403307)
Cod sursa(job #403307)
#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;
}