Pagini recente » Cod sursa (job #1852789) | Cod sursa (job #3204998) | Cod sursa (job #1228189) | Cod sursa (job #382938) | Cod sursa (job #2392448)
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
using namespace std ;
const int NR = 850 , oo = 1000000005 ;
ifstream in ("adapost.in") ;
ofstream out ("adapost.out") ;
vector < int > v [ NR ] ;
vector < double > d ( NR ) , edge ;
int n , x , t [ NR ] , st , dr , mid ;
double cost [ NR ][ NR ] , cap [ NR ][ NR ] , limit , best , maxedge , ans = 1000000005 ;
pair < double , double > p [ NR ] , ad [ NR ] ;
double sol ;
bool inq [ NR ] ;
struct cmp {
inline bool operator() ( const int i , const int j ) {
return d [ i ] > d [ j ] ;
}
};
priority_queue < int , vector < int > , cmp > q ;
bool dijkstra ( ) {
int nod , i ;
for ( i = 1 ; i <= 2 * n + 1 ; ++ i ) d [ i ] = oo ;
d [ 0 ] = 0 ;
q.push( 0 ) ;
while ( !q.empty() ) {
nod = q.top() ;
q.pop() ;
inq [ nod ] = 0 ;
for ( vector < int > :: iterator it = v [ nod ].begin() ; it != v [ nod ].end() ; ++ it )
if ( cap [ nod ][ *it ] ) {
if ( d [ nod ] + cost [ nod ][ *it ] >= 0 && d [ nod ] + cost [ nod ][ *it ] < d [ *it ] && ( abs ( cost [ nod ][ *it ] ) <= limit || !cost [ nod ][ *it ] ) ) {
d [ *it ] = d [ nod ] + cost [ nod ][ *it ] ;
q.push( *it ) ;
t [ *it ] = nod ;
}
}
}
if ( d [ n << 1 | 1 ] == oo ) return 0 ;
nod = 2*n + 1 ;
while ( nod ) {
cap [ t [ nod ] ][ nod ] = 0 ;
cap [ nod ][ t [ nod ] ] = 1 ;
nod = t [ nod ] ;
}
maxedge = max ( maxedge , d[ n << 1 | 1 ] ) ;
sol += d[ n << 1 | 1 ] ;
return 1 ;
}
int main () {
int i , j ;
in >> n ;
for ( i = 1 ; i <= n ; ++ i ) {
in >> p [ i ].f >> p [ i ].s ;
}
for ( i = 1 ; i <= n ; ++ i ) {
in >> ad [ i ].f >> ad [ i ].s ;
}
for ( i = 1 ; i <= n ; ++ i )
for ( j = 1 ; j <= n ; ++ j ) {
cost [ i ][ j + n ] = sqrt ( ( ad [ i ].f - p [ j ].f ) * ( ad [ i ].f - p [ j ].f ) + ( ad [ i ].s - p [ j ].s ) * ( ad [ i ].s - p [ j ].s ) ) ;
cap [ i ][ j + n ] = 1 ;
edge.pb ( cost [ i ][ j + n ] ) ;
cost [ j + n ][ i ] = - cost [ i ][ j + n ] ;
v [ i ].pb ( j + n ) ;
v [ j + n ].pb ( i ) ;
}
for ( i = 1 ; i <= n ; ++ i ) {
cap [ 0 ][ i ] = 1 ;
v [ 0 ].pb ( i ) ;
v [ i ].pb ( 0 ) ;
cap [ i + n ][ n << 1 | 1 ] = 1 ;
v [ i + n ].pb ( n << 1 | 1 ) ;
v [ n << 1 | 1 ].pb ( i + n ) ;
}
sort ( edge.begin() , edge.end() ) ;
limit = edge [ edge.size() - 1 ] ;
while ( dijkstra() ) ;
ans = min ( maxedge , ans ) ;
best = sol ;
st = 0 ;
dr = edge.size() - 1 ;
while ( st < dr ) {
if ( dr == st + 1 ) {
sol = 0 ;
mid = dr ;
limit = edge [ mid ] ;
for ( i = 1 ; i <= n ; ++ i )
for ( j = 1 ; j <= n ; ++ j )
cap [ i ][ j + n ] = 1 , cap [ j + n ][ i ] = 0 ;
for ( i = 1 ; i <= n ; ++ i ) cap [ 0 ][ i ] = 1 , cap [ i ][ 0 ] = 0 , cap [ i + n ][ 2 * n + 1 ] = 1 , cap [ 2 * n + 1 ][ i + n ] = 0 ;
maxedge = 0 ;
while ( dijkstra() ) ;
if ( sol == best ) ans = min ( edge [ mid ] , ans ) ;
sol = 0 ;
mid = st ;
limit = edge [ mid ] ;
for ( i = 1 ; i <= n ; ++ i )
for ( j = 1 ; j <= n ; ++ j )
cap [ i ][ j + n ] = 1 , cap [ j + n ][ i ] = 0 ;
for ( i = 1 ; i <= n ; ++ i ) cap [ 0 ][ i ] = 1 , cap [ i ][ 0 ] = 0 , cap [ i + n ][ 2 * n + 1 ] = 1 , cap [ 2 * n + 1 ][ i + n ] = 0 ;
maxedge = 0 ;
while ( dijkstra() ) ;
if ( sol == best ) ans = min ( edge [ mid ] , ans ) ;
break ;
}
mid = ( st + dr ) >> 1 ;
sol = 0 ;
limit = edge [ mid ] ;
for ( i = 1 ; i <= n ; ++ i )
for ( j = 1 ; j <= n ; ++ j )
cap [ i ][ j + n ] = 1 , cap [ j + n ][ i ] = 0 ;
for ( i = 1 ; i <= n ; ++ i ) cap [ 0 ][ i ] = 1 , cap [ i ][ 0 ] = 0 , cap [ i + n ][ 2 * n + 1 ] = 1 , cap [ 2 * n + 1 ][ i + n ] = 0 ;
maxedge = 0 ;
while ( dijkstra() ) ;
if ( sol == best ) ans = min ( edge [ mid ] , ans ) , dr = mid - 1 ;
else st = mid + 1 ;
}
out << fixed << setprecision( 7 ) << ans << ' ' << best << '\n' ;
}