Cod sursa(job #17464)

Utilizator gcosminGheorghe Cosmin gcosmin Data 15 februarie 2007 22:31:46
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

#define NMAX 410
#define INF 1000000000
#define eps 0.0001

int N;

double xx[NMAX];
double yy[NMAX];
double xxa[NMAX];
double yya[NMAX];

pair <double, int> leg[NMAX][NMAX];

vector <pair<int, double> > lg[NMAX * 2];

int cap[NMAX * 2][NMAX * 2];

char viz[NMAX];
int st[NMAX];

int pair_up(int x, double max)
{
	if (viz[x]) return 0;

	viz[x] = 1;

	for (int i = 1; i <= N && leg[x][i].first <= max; i++)
		if (!st[ leg[x][i].second ] || pair_up(st[ leg[x][i].second ], max)) {
			st[ leg[x][i].second ] = x;
			return 1;
		}

return 0;
}

int cuplaj(double max)
{
	int i;

	memset(viz, 0, sizeof(viz));
	memset(st, 0, sizeof(st));

	for (i = 1; i <= N; i++)
		if (!pair_up(i, max)) {
			memset(viz, 0, sizeof(viz));
			pair_up(i, max);
		}

	int rez = 0;

	for (i = 1; i <= N; i++) rez += st[i] > 0;

return rez;
}

int coada[NMAX * NMAX * 4];
double dist[NMAX * 2];
int pred[NMAX * 2];
char in_coada[NMAX * 2];

int bf()
{
	memset(in_coada, 0, sizeof(viz));

	int p, q, i, x, y;

	for (i = 1; i <= 2 * N + 1; i++) dist[i] = INF;

	p = q = 0;
	coada[0] = 0;

	vector <pair<int, double> > :: iterator it;

	while (p <= q) {
		x = coada[p];
		p++;
		in_coada[x] = 0;

		for (it = lg[x].begin(); it != lg[x].end(); it++) {
			y = (*it).first;
			if (dist[x] + (*it).second < dist[y] && cap[x][y]) {
				dist[y] = dist[x] + (*it).second;
				pred[y] = x;
				if (!in_coada[y]) coada[++q] = y, in_coada[y] = 1;
			}
		}
	}

return dist[2 * N + 1] < INF;	
}


double baga_flux_cu_cost(double max)
{
	int i, cur, j;

	// fac graful

	for (i = 1; i <= N; i++) {
		lg[0].push_back(make_pair(i, 0));
		cap[0][i] = 1;
	}

	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++) {
			if (leg[i][j].first <= max) {
				lg[i].push_back(make_pair(leg[i][j].second + N, leg[i][j].first));
				cap[i][leg[i][j].second + N] = 1;

				lg[leg[i][j].second + N].push_back(make_pair(i, -leg[i][j].first));			
			}
		}

	for (i = 1; i <= N; i++) {
		lg[i + N].push_back(make_pair(2 * N + 1, 0));
		cap[i + N][2 * N + 1] = 1;
	}

	double rez = 0;

	while (bf()) {
		rez += dist[2 * N + 1];

		cur = 2 * N + 1;

		while (cur) {
			cap[pred[cur]][cur]--;
			cap[cur][pred[cur]]++;
			cur = pred[cur];
		}
	}

return rez;		
}

int main()
{
	int i, j;
	
	freopen("adapost.in", "r", stdin);
	freopen("adapost.out", "w", stdout);

	scanf("%d", &N);

	for (i = 1; i <= N; i++) scanf("%lf %lf", &xx[i], &yy[i]);
	for (i = 1; i <= N; i++) scanf("%lf %lf", &xxa[i], &yya[i]);

	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++)
			leg[i][j] = make_pair( sqrt( (xx[i] - xxa[j]) * (xx[i] - xxa[j]) + (yy[i] - yya[j]) * (yy[i] - yya[j]) ), j );
		sort(leg[i] + 1, leg[i] + N + 1);
	}

	double step;

	for (step = 1; step <= 1000; step *= 2);

	// caut maximul minim

	double rez = 0;

	for (; step > 0.00001; step *= 0.5)
		if (cuplaj(rez + step) < N)
			rez += step;	

	printf("%lf %lf\n", rez, baga_flux_cu_cost(rez + eps));

fclose(stdin);
fclose(stdout);
return 0;
}