Cod sursa(job #93136)

Utilizator MariusMarius Stroe Marius Data 17 octombrie 2007 20:17:03
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <memory.h>

using namespace std;

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

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

int n;

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

vector <int> V;

vector <int> G[MAX_N];

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


void read_in(void)
{
	int a, b, c, d;

	scanf("%d", &n);
	for (int i = 0; i < n; ++ i) {
		scanf("%d.%d %d.%d", &a, &b, &c, &d);
		S[i][0] = a * 1000 + b;
		S[i][1] = c * 1000 + d;
	}
	for (int i = 0; i < n; ++ i) {
		scanf("%d.%d %d.%d", &a, &b, &c, &d);
		A[i][0] = a * 1000 + b;
		A[i][1] = c * 1000 + d;
	}
}

int pairup(int n)
{
	if (u[n])  
		return 0;
	u[n] = 1;
	vector <int>::iterator it;
	for (it = G[n].begin(); it != G[n].end(); ++ it) {
		if (!l[*it]) {
			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 int max_cost)
{
	int cnt = 0;

	for (int i = 0; i < n; ++ i) {
		l[i] = r[i] = u[i] = 0;
		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, 0, sizeof(u));
			cnt += pairup(i);
		} else
			cnt ++;
	}
	return cnt;
}

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] = int(sqrt(sqr(double(S[i][0] - A[j][0])) + sqr(double(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("%d.%03d", V[k] / 1000, V[k] % 1000);

	return 0;
}