Cod sursa(job #93409)

Utilizator MariusMarius Stroe Marius Data 18 octombrie 2007 19:09:07
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.5 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <memory.h>
#include <queue>

using namespace std;

const char iname[] = "adapost.in";
const char oname[] = "adapost.out";

#define MAX_N  400
#define sqr(z) ((z) * (z))

int n;

double S[MAX_N][2], A[MAX_N][2], D[MAX_N][MAX_N];

vector <double> V;

vector <int> G[MAX_N], H[MAX_N * 2 + 5];

queue <int> Q;

int l[MAX_N], r[MAX_N], u[MAX_N];

int C[MAX_N * 2 + 5][MAX_N * 2 + 5];


void read_in(void)
{
	scanf("%d", &n);
	for (int i = 0; i < n; ++ i)
		scanf("%lf %lf", &S[i][0], &S[i][1]);
	for (int i = 0; i < n; ++ i)
		scanf("%lf %lf", &A[i][0], &A[i][1]);
}

int pairup(int n)
{
	if (u[n] != -1)  
		return 0;
	u[n] = 1;
	vector <int>::iterator it;
	for (it = G[n].begin(); it != G[n].end(); ++ it) {
		if (l[*it] == -1) {
			l[*it] = n;
			r[n] = *it;
			return 1;
		}
	}
	for (it = G[n].begin(); it != G[n].end(); ++ it) {
		if (pairup(l[*it])) {
			l[*it] = n;
			r[n] = *it;
			return 1;
		}
	}
	return 0;
}

int solve(const double max_cost)
{
	int cnt = 0;

	for (int i = 0; i < n; ++ i) {
		l[i] = r[i] = u[i] = -1;
		vector <int> ().swap(G[i]);
	}
	for (int s = 0; s < n; ++ s) {
		for (int a = 0; a < n; ++ a) if (max_cost >= D[s][a])
			G[s].push_back(a);
	}
	for (int i = 0; i < n; ++ i) {
		if (!pairup(i)) {
			memset(u, -1, sizeof(u));
			cnt += pairup(i);
		} else
			cnt ++;
	}
	return cnt;
}

double bellman_ford(const double max_cost)
{
	for (int s = 0; s < n; ++ s) {
		for (int a = 0; a < n; ++ a)
			if (::D[s][a] <= max_cost) {
				H[s + 1].push_back(n + a + 1);
				H[n + a + 1].push_back(s + 1);
				C[s + 1][n + a + 1] = 1;
			}
	}
	for (int s = 1; s <= n; ++ s)
		H[0].push_back(s), C[0][s] = 1;
	for (int a = n + 1; a <= 2 * n; ++ a)
		H[a].push_back(2 * n + 1), C[a][2 * n + 1] = 1;
	
	double D[2 * MAX_N + 5];
	int T[2 * MAX_N + 5];

	for (int stp = 1; stp <= n; ++ stp) {
		for (int i = 1; i <= 2*n+1; ++ i) {
			D[i] = 1e9;
			T[i] = -1;
		}
		D[0] = 0;
		Q.push(0);
		while (!Q.empty()) {
			int x = Q.front();
			Q.pop();
			for (size_t i = 0; i < H[x].size(); ++ i) {
				int y = H[x][i];
				if (C[x][y] != 1)
					continue ;
				double cost_of_edge;
				if (!x || y == 2*n+1)
					cost_of_edge = 0;
				else if (x <= n)
					cost_of_edge = ::D[x - 1][y - n - 1];
				else if (x >= n + 1)
					cost_of_edge = -(::D[y - 1][x - n - 1]);

				if (D[y] > D[x] + cost_of_edge) {
					D[y] = D[x] + cost_of_edge;
					T[y] = x;
					Q.push(y);
				}
			}
		}
		for (int x = 2*n+1; x != 0; x = T[x]) {
			if (T[x] == 0 || x == 2*n+1)
				C[T[x]][x] = 0;
			else {
				C[T[x]][x] = C[T[x]][x] == 1 ? 0 : 1;
				C[x][T[x]] = C[x][T[x]] == 1 ? 0 : 1;
			}
		}
	}

	double res = 0;
	for (int x = 1; x <= n; ++ x) {
		for (size_t i = 0; i < H[x].size(); ++ i) {
			int y = H[x][i];
			res += ::D[x - 1][y - n - 1] * (1 - C[x][y]);
		}
	}
	return res;
}

int main(void)
{
	freopen(iname, "r", stdin);
	freopen(oname, "w", stdout);

	read_in();
	for (int i = 0; i < n; ++ i) {
		for (int j = 0; j < n; ++ j) {
			D[i][j] = sqrt(sqr(S[i][0] - A[j][0]) + sqr(S[i][1] - A[j][1]));
			V.push_back(D[i][j]);
		}
	}
	sort(V.begin(), V.end());
	int delta, k;
	for (delta = 1; delta < n * n; delta <<= 1) ;
	for (k = 0; delta; delta >>= 1) {
		if ((k + delta) < n * n && solve(V[k + delta]) < n)
			k += delta;
	}
	if (solve(V[k]) < n)
		k ++;
	printf("%.5lf %.5lf", V[k], bellman_ford(V[k]));

	return 0;
}