Cod sursa(job #419480)

Utilizator FlorianFlorian Marcu Florian Data 17 martie 2010 16:14:23
Problema Adapost Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
using namespace std;
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<queue>
#define pb push_back
#define EPS 1e-14
#define oo 0x3f3f3f3f
const int MAX_N = 804;
double cst[MAX_N][MAX_N];
short int capac[MAX_N][MAX_N];
int N,P, S, D;
bool viz[MAX_N]; queue<int>Q;
double CST, LIM;
int st[MAX_N], dr[MAX_N];
double d[MAX_N], A[401*402], X[MAX_N], Y[MAX_N];
inline int comp(double a, double b)
{
	if (a + EPS < b) return 1;
	if (b + EPS < a) return -1;
	return 0;
}
inline double dist(double a, double b, double c, double d)
{
	return sqrt( (a - c)*(a-c) + (b-d)*(b-d) );
}
struct cmp
{
	bool operator()(const double &a, const double &b)const
	{
		int r = comp(a,b);
		if( r == 1) return 1;
		return 0;
	}
};
short int tata[MAX_N];
int BFS()
{
	int x, y, i;
	for(i = 1; i <= D; ++i) d[i] = oo, viz[i] = false, tata[i] = 0;
	for( Q.push(S); !Q.empty(); Q.pop() )
	{
		x = Q.front(); viz[x] = false;
		for(y = S; y <= D; ++y)
		{
			if( capac[x][y] && cst[x][y] <= LIM && comp(d[y] , d[x] + cst[x][y]) == -1 )
			{
				d[y] = d[x] + cst[x][y];
				tata[y] = x;
				if( viz[y] ) continue;
				viz[y] = true;				
				Q.push(y);
			}
		}
	}
	if( d[D] == oo ) return 0;
	return 1;
}
void flux()
{
	int i, f;
	for(;BFS();)
	{
		f = oo;
		for(i = D; i != S; i = tata[i])
			if(f > capac[tata[i]][i]) f = capac[tata[i]][i];
		for(i = D; i != S; i =tata[i])
		{
			capac[tata[i]][i] -=f;
			capac[i][tata[i]] +=f;
		}
		CST += (double)f * d[D];
	}
}
int pairUp(int x)
{
	if(viz[x]) return 0;
	int y;
	viz[x] = 1;
	for(y = N+1; y <= 2*N; ++y)
	{
		if( comp(cst[x][y] , LIM) == -1 || capac[x][y] == 0) continue;
		if( !st[y] )
		{
			st[y] = x;
			dr[x] = y;
			return 1;
		}
	}
	for(y = N+1; y <= 2*N; ++y)
	{
		if( comp(cst[x][y] , LIM) == -1 || capac[x][y] == 0) continue;
		if( pairUp(st[y]) )
		{
			st[y] = x;
			dr[x] = y;
			return 1;
		}
	}
	return 0;
}
inline int pot(double lim)
{
	CST = 0;
	LIM = lim;
	int nr = 0, i, ok;
	memset(st,0,sizeof(st));
	memset(dr,0,sizeof(dr));
	for(ok = 1; ok;)
	{
		ok = 0;
		memset(viz, 0, sizeof(viz));
		for(i = 1; i <= N; ++i)
			if( !dr[i] ) ok|=pairUp(i);
	}
	for(i = 1; i <= N; ++i)
		if(dr[i]) ++nr;
	if(nr == N) return 1;
	return 0;
}
int main()
{
	ifstream in("adapost.in"); ofstream out("adapost.out");
	int st, dr, i, j, m, r, p;
	double x,y, d;
	in>>N;
	S = 0; D = N + N + 1;
	for(i = 1; i <= N; ++i) in>>X[i]>>Y[i];	
	for(i = 1; i <= N; ++i)
	{
		in>>x>>y;
		capac[S][i] = 1; 
		capac[i+N][D] = 1;
		for(j = 1; j <= N; ++j)
		{
			d = dist(x, y, X[j], Y[j]);
			cst[i][j+N] = d; cst[j+N][i] = -d;
			capac[i][j + N] = 1;
			A[P++] = d;
		}
	}
	sort(A, A + P, cmp());
	st = 0; dr = P - 1;
	while(st<=dr)
	{
		m = (st + dr)>>1;
		if(m) p = pot(A[m-1]);
		else p = 0;
		r = pot(A[m]); 
		if( r && !p ) 
		{ 
			flux();
			out<<setprecision(5)<<fixed<<A[m]<<" "<<CST<<"\n"; 
			return 0; }
		else if( r && p ) dr = m - 1;
		else st = m + 1;
	}
	return 0;
}