Cod sursa(job #402581)

Utilizator Mishu91Andrei Misarca Mishu91 Data 23 februarie 2010 23:01:32
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 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 = 405;

int N, M, C[MAX_N], R[MAX_N];
pair <double, double> S[MAX_N], A[MAX_N];
double L[MAX_N][MAX_N], T[MAX_N * 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]);
			T[++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;
}

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

	citire();

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

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