Cod sursa(job #977993)

Utilizator tudorv96Tudor Varan tudorv96 Data 27 iulie 2013 13:19:22
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;

ifstream fin ("adapost.in");
ofstream fout ("adapost.out");

const double oo = 2e9, er = 1e-4;
const int N = 810, d = 805;

#define xx first
#define yy second

typedef pair <double, double> coord;

int C[N][N], n, t[N], cuplaj, A[N], B[N];
double cost[N][N], cst, dmin = oo, v[N*N/4], c[N];
coord memleft[N], memright[N];
queue <int> Q;
bool q[N], viz[N];
vector <int> g[N];

bool match(int x) {
	if (viz[x])
		return 0;
	viz[x] = 1;
	for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
		if (!B[*it]) {
			B[*it] = x;
			A[x] = *it;
			cuplaj++;
			return 1;
		}
	for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
		if (B[*it] != x && match(B[*it])) {
			B[*it] = x;
			A[x] = *it;
			return 1;
		}
	return 0;
}

bool go(double x) {
	for (int i = 1; i <= n; ++i)
		vector <int> ().swap(g[i]);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j) {
			if (cost[i][n+j] <= x + er)
				g[i].push_back(j);
		}
	for (int i = 1; i <= n; ++i) 
		viz[i] = 0, A[i] = B[i] = 0;
	cuplaj = 0;
	bool ok = 1;
	while (ok) {
		ok = 0;
		for (int i = 1; i <= n; ++i)
			viz[i] = 0;
		for (int i = 1; i <= n; ++i)
			if (!A[i])
				ok |= match(i);
	}
	return (cuplaj == n);
}

bool bellmanford() {
	Q.push(0);
	for (int i = 1; i <= n * 2; ++i)
		c[i] = oo;
	c[d] = oo;
	while (Q.size()) {
		int x = Q.front(); Q.pop();
		q[x] = 0;
		for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it) {
			if (C[x][*it]) {
				double NEW = c[x] + cost[x][*it];
				if (NEW < c[*it] + er) {
					c[*it] = NEW;
					t[*it] = x;
					if (!q[*it]) {
						q[*it] = 1;
						Q.push(*it);
					}
				}
			}
		}
	}
	return (c[d] != oo);
}

int main() {
	fin >> n;
	for (int i = 1; i <= n; ++i)
		fin >> memleft[i].xx >> memleft[i].yy;
	for (int i = 1; i <= n; ++i)
		fin >> memright[i].xx >> memright[i].yy;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j) {
			double now = sqrt ((memleft[i].xx - memright[j].xx) * (memleft[i].xx - memright[j].xx) + (memleft[i].yy - memright[j].yy) * (memleft[i].yy - memright[j].yy));
			cost[i][n+j] = now;
			cost[n+j][i] = -now;
			v[(i - 1) * n + j - 1] = now;
		} 
	sort (v, v + n * n);
	int lo = 0, hi = n * n;
	while (lo < hi) {
		int mid = (lo + hi) >> 1;
		if (go(v[mid])) {
			dmin = min (dmin, v[mid]);
			hi = mid;
		}
		else
			lo = mid + 1;
	}
	for (int i = 1; i <= n; ++i)
		vector <int> ().swap(g[i]);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j) {
			if (cost[i][n+j] <= dmin + er) {
				g[i].push_back(n + j); g[n + j].push_back(i);
				C[i][n + j] = 1;
			}
		}
	for (int i = 1; i <= n; ++i) {
		g[0].push_back(i);
		C[0][i] = 1;
		g[n+i].push_back(d);
		C[n+i][d] = 1;
	}
	while (bellmanford()) {
		cst += c[d];
		for (int x = d; x; x = t[x])
			C[t[x]][x]--, C[x][t[x]]++;
	}
	fout << fixed << setprecision(5) << dmin << " " << cst;
	fout.close();
}