Pagini recente » Cod sursa (job #85568) | Monitorul de evaluare | Cod sursa (job #1670543) | Monitorul de evaluare | Cod sursa (job #1787789)
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <vector>
#include <deque>
#include <tuple>
#include <iomanip>
#include <cstring>
#include <climits>
#include <cmath>
using namespace std;
ifstream in ( "adapost.in" );
ofstream out( "adapost.out" );
const int DIM = 8e3 + 5;
const int INF = 0x3f3f3f3f;
vector< pair<double, double> > pts; vector< tuple<double, int, int> > edg; vector<int> e[DIM]; bitset<DIM> ma, adj[DIM];
double dst[DIM][DIM], dp[DIM]; int cap[DIM][DIM], flo[DIM][DIM], l[DIM], r[DIM], fth[DIM];
bool cmp( tuple<double, int, int> t1, tuple<double, int, int> t2 ) {
return get<0>(t1) < get<0>(t2); }
bool couple( int x, int n, int &cnt ) {
if( ma[x] == 1 ) { return false; } ma[x] = 1;
for( int y = 1; y <= n; y ++ ) { if( adj[x][y] == 1 && r[y] == 0 ) { l[x] = y; r[y] = x; cnt += 1; return true; } }
for( int y = 1; y <= n; y ++ ) { if( adj[x][y] == 1 && couple(r[y], n, cnt) ) { l[x] = y; r[y] = x; cnt += 0; return true; } }
return false; }
bool solve( int n, int k ) {
fill( l + 1, l + n + 1, 0 ); fill( r + 1, r + n + 1, 0 );
for( int i = 1; i <= n; i ++ ) {
adj[i].reset(); }
for( int i = 0; i <= k; i ++ ) {
adj[ get<1>(edg[i]) ][ get<2>(edg[i]) ] = 1; }
int ok, cnt = 0;
do {
ok = 0; ma.reset();
for( int i = 1; i <= n; i ++ ) {
if( l[i] == 0 && couple(i, n, cnt) ) ok = 1; }
} while( ok == 1 );
return ( n == cnt ); }
bool bfs( int st, int fi ) {
fill( fth + 1, fth + fi + 1, 0 ); fill( dp + 1, dp + fi + 1, INT_MAX );
deque<int> que; ma.reset(); ma[st] = 1; que.push_back( st ); bool ok = 0;
while( que.empty() == 0 ) {
int x = que.front(); que.pop_front(); ma[x] = 0;
for( auto y : e[x] ) {
if( flo[x][y] < cap[x][y] && dp[y] > dp[x] + dst[x][y] ) {
dp[y] = dp[x] + dst[x][y]; fth[y] = x;
if( ma[y] == 0 ) {
ma[y] = 1; que.push_back( y );
if( y == fi ) ok = 1; } } } }
return ok;
}
int main( int argc, const char *argv[] ) {
int n; in >> n;
for( int i = 0; i < n; i ++ ) {
double x, y; in >> x >> y;
pts.push_back( make_pair(x, y) ); }
for( int i = 0; i < n; i ++ ) {
double x, y; in >> x >> y;
for( int j = 0; j < n; j ++ ) {
edg.push_back( make_tuple( hypot( fabs(x - pts[j].first ), fabs(y - pts[j].second) ), j + 1, i + 1 ) ); } }
sort( edg.begin(), edg.end(), cmp );
int st = 0, fi = n * n - 1, mid;
while( st <= fi ) {
mid = st + ( fi - st ) / 2;
( solve(n, mid) ) ? ( fi = mid - 1 ) : ( st = mid + 1 ); }
for( int i = 1; i <= n; i ++ ) {
cap[0][i] = 1; cap[i + n][n * 2 + 1] = 1;
e[0].push_back( i ); e[i + n].push_back( n * 2 + 1 );
e[i].push_back( 0 ); e[n * 2 + 1].push_back( i + n ); }
for( int i = 0; i <= st; i ++ ) {
double d = get<0>(edg[i]); int x = get<1>(edg[i]), y = get<2>(edg[i]);
cap[x][y + n] = 1; dst[x][y + n] = d; dst[y + n][x] = -d;
e[x].push_back( y + n ); e[y + n].push_back( x ); }
double ans = 0;
while( bfs(0, n * 2 + 1) ) {
int minim = INT_MAX;
for( int x = n * 2 + 1; x != 0; x = fth[x] )
minim = min( minim, cap[ fth[x] ][x] - flo[ fth[x] ][x] );
for( int x = n * 2 + 1; x != 0; x = fth[x] ) {
ans += minim * 1.0 * dst[ fth[x] ][x]; flo[ fth[x] ][x] += minim; flo[x][ fth[x] ] -= minim; } }
out << setprecision(5) << fixed << get<0>(edg[st]) << " " << ans << endl;
return 0; }