Cod sursa(job #48059)

Utilizator TYTUSVlad Saveluc TYTUS Data 4 aprilie 2007 13:06:05
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<double, double>point;

const int NMAX = 401;
const double eps = 1.0e-3;

point s[NMAX], ad[NMAX];
double d[NMAX][NMAX];
int cap[2 * NMAX][2 * NMAX];
vector<int>lv[2 * NMAX];

int n;

inline double sqr(double x) {
	return x * x;
}

int pi[2 * NMAX], q[2 * NMAX];
int bf() {
	int l, r;
	q[0] = 0;
	memset(pi, -1, 8 * NMAX);
	pi[0] = 0;
	for (l = 0, r = 1; l < r; ++l) {
		vector<int>::iterator it;
// 		printf ("%d\n", q[l]);
		for (it = lv[q[l]].begin(); it != lv[q[l]].end(); ++it) {
			if (cap[q[l]][*it] && pi[*it] == -1) {
// 				printf ("--%d\n", *it);
				q[r++] = *it;
				pi[*it] = q[l];
				if ((*it) == 2 * n + 1) {
					return 1;
				}
			}
		}
	}
	return 0;
}
	

int flow(double lim) {
	int i, j, ret = 0;
	lv[0].clear();
	lv[2 * n + 1].clear();
	for (i = 1; i <= n; ++i) {
		lv[i].clear();
		lv[0].push_back(i);
		lv[i].push_back(0);
		lv[n + i].clear();
		lv[n + i].push_back(2 * n + 1);
		lv[2 * n + 1].push_back(n + i);
	}
	
	for (i = 1; i <= n; ++i) {
		cap[0][i] = 1;
		cap[i][0] = 0;
		cap[n + i][2 * n + 1] = 1;
		cap[2 * n + 1][n + i] = 0;
		for (j = 1; j <= n; ++j) {
			if (d[i][j] <= lim) {
				cap[i][n + j] = 1;
				lv[i].push_back(n + j);
				lv[n + j].push_back(i);
			} else {
				cap[i][n + j] = 0;
			}
			cap[n + j][i] = 0;
		}
	}
	//Pun muchii cu greedy
	for (i = 1; i <= n; ++i) {
		for (j = n + 1; j <= 2 * n; ++j) {
			if (cap[i][j] && cap[j][2 * n + 1]) {
				cap[0][i] = 0;
				cap[i][0] = 1;
				cap[i][j] = 0;
				cap[j][i] = 1;
				cap[j][2 * n + 1] = 0;
				cap[2 * n + 1][j] = 1;
				ret++;
				break;
			}
		}
	}
	//Fluxul propriu-zis
	while (bf()) {
		int nod = 2 * n + 1;
		while (nod != 0) {
//  			printf ("Nod = %d\n", nod);
			cap[nod][pi[nod]] = 1;
			cap[pi[nod]][nod] = 0;
			nod = pi[nod];
		}
		ret++;
	}
	return ret >= n ? 1 : 0; //De fapt era ret == n ? 1 : 0
}

int main() {
	FILE *fin = fopen ("adapost.in", "r");
	FILE *fout = fopen ("adapost.out", "w");
	fscanf (fin, "%d", &n);
	int i, j;
	for (i = 1; i <= n; ++i) {
		fscanf (fin, "%lf %lf", &s[i].first, &s[i].second);
	}
	for (i = 1; i <= n; ++i) {
		fscanf (fin, "%lf %lf", &ad[i].first, &ad[i].second);
	}
	vector<double>allV;
	for (i = 1; i <= n; ++i) {
		for (j = 1; j <= n; ++j) {
			d[i][j] = sqrt(sqr(s[i].first - ad[j].first) + sqr(s[i].second - ad[j].second));
			allV.push_back(d[i][j]);
		}
	}
	sort(allV.begin(), allV.end());
	int sol = allV.size() - 1, step;
	for (step = 1; (step << 1) < allV.size(); step <<=1);
	for (; step; step>>=1) {
		if (sol - step >= 0 && flow(allV[sol - step])) {
			sol -= step;
		}
	}
	fprintf (fout, "%lf 0\n", allV[sol]);
	fclose(fout);
	return 0;
}