Cod sursa(job #402641)

Utilizator Mishu91Andrei Misarca Mishu91 Data 24 februarie 2010 00:03:40
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

#define x first
#define y second
#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)

const int MAX_N = 805;
const double INF = 0x3f3f3f3f;

int nr, N, M, C[MAX_N], R[MAX_N], P, U, Cap[MAX_N][MAX_N], F[MAX_N][MAX_N], T[MAX_N];
pair <double, double> S[MAX_N], A[MAX_N];
double L[MAX_N][MAX_N], E[MAX_N * MAX_N], Cost[MAX_N][MAX_N], D[MAX_N];
char viz[MAX_N];
vector <int> G[MAX_N];

inline double dist(pair <double, double> &a, pair <double, double> &b)
{
	double dx = (a.x - b.x) * (a.x - b.x);
	double dy = (a.y - b.y) * (a.y - b.y);

	return sqrt(dx + dy);
}

void citire()
{
	scanf("%d\n", &N);

	for(int i = 1; i <= N; ++i)
		scanf("%lf %lf\n", &S[i].x, &S[i].y);

	for(int i = 1; i <= N; ++i)
		scanf("%lf %lf\n", &A[i].x, &A[i].y);

	for(int i = 1; i <= N; ++i)
	{
		for(int j = 1; j <= N; ++j)
		{
			L[i][j] = dist(S[i], A[j]);
			E[++M] = L[i][j];
		}
	}
}

bool pairup(int nod)
{
	if(viz[nod]) return 0;
	viz[nod] = 1;

	foreach(G[nod])
		if(!R[*it])
		{
			C[nod] = *it;
			R[*it] = nod;
			return 1;
		}

	foreach(G[nod])
		if(pairup(R[*it]))
		{
			C[nod] = *it;
			R[*it] = nod;
			return 1;
		}

	return 0;
}

inline bool cuplaj(double x)
{
	for(int i = 1; i <= N; ++i)
	{
		G[i].clear();
		for(int j = 1; j <= N; ++j)
			if(x >= L[i][j])
				G[i].push_back(j);
	}

	memset(C, 0, sizeof C);
	memset(R, 0, sizeof R);

	bool ok = 1;
	while(ok)
	{
		ok = 0;
		memset(viz, 0, sizeof viz);

		for(int i = 1; i <= N; ++i)
			if(!C[i])
				ok |= pairup(i);
	}

	for(int i = 1; i <= N; ++i)
		if(!C[i])
			return 0;
	return 1;
}

struct cmp
{
	bool operator()(const int &a, const int &b) const
	{
		return D[a] > D[b];
	}
};

inline bool dijkstra()
{
	priority_queue <int, vector <int>, cmp> Q;
	memset(viz, 0, sizeof viz);
	for(int i = 1; i <= U; ++i)
		D[i] = INF;

	D[P] = 0;
	Q.push(P);
	viz[P] = 1;

	while(!Q.empty())
	{
		int nod = Q.top();
		Q.pop();
		viz[nod] = 0;

		foreach(G[nod])
		{
			if((D[*it] > D[nod] + Cost[nod][*it]) && (Cap[nod][*it] > F[nod][*it]))
			{
				D[*it] = D[nod] + Cost[nod][*it];
				T[*it] = nod;

				if(viz[*it]) continue;

				viz[*it] = 1;
				Q.push(*it);
			}
		}
	}

	return (D[U] != INF);
}

double flux(double x)
{
	P = 0, U = 2*N+1;
	for(int i = 1; i <= N; ++i)
	{
		G[i].clear();
		for(int j = 1; j <= N; ++j)
			if(L[i][j] <= x)
			{
				Cap[i][j+N] = 1;
				Cost[i][j+N] = L[i][j];
				Cost[j+N][i] = -L[i][j];
				G[i].push_back(j+N);
				G[j+N].push_back(i);
			}
	}

	for(int i = 1; i <= N; ++i)
	{
		Cap[P][i] = 1;
		G[i].push_back(P);
		G[P].push_back(i);
	
		Cap[i+N][U] = 1;
		G[i+N].push_back(U);
		G[U].push_back(i+N);
	}

	double flow = 0.0;

	while(dijkstra())
	{
		for(int i = U; i; i = T[i])
			F[T[i]][i]++,
			F[i][T[i]]--;

		flow += D[U];
	}

	return flow;
}

int main()
{
	freopen("adapost.in", "rt", stdin);
	freopen("adapost.out", "wt", stdout);

	citire();

	sort(E+1, E+M+1);
	int i = M;
	for(int lg = (1 << 18); lg; lg >>= 1)
		if(i - lg > 0 && cuplaj(E[i-lg]))
			i -= lg;

	printf("%.5lf %.5lf\n", E[i], flux(E[i]));
}