Cod sursa(job #420386)

Utilizator FlorianFlorian Marcu Florian Data 18 martie 2010 22:20:40
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
using namespace std;
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<vector>
#include<queue>
#define pb push_back
#define oo 0x3f3f3f3f
const int MAX_N = 805;
vector<int>G[MAX_N];
double cst[MAX_N][MAX_N];
short int capac[MAX_N][MAX_N];
int N,P, S, D;
bool viz[MAX_N];
double CST, LIM, cin[MAX_N][MAX_N];
int st[MAX_N], dr[MAX_N];
double d[MAX_N], A[401*402], X[MAX_N], Y[MAX_N];
inline double dist(double &a, double &b, double &c, double &d)
{
	return sqrt( (a - c)*(a-c) + (b-d)*(b-d) );
}

short int tata[MAX_N];
struct cmp 
{ 
	bool operator()(const int &a, const int &b) 
	{ 
		return d[a]>d[b];
	} 
};
int BFS()
{
	int x, y, i;
	priority_queue <int, vector <int>, cmp > Q; 
	for(i = 0; i <= D; ++i) d[i] = oo, tata[i] = 0, viz[i]=0;
	d[S] = 0;
	Q.push(S);
	while( !Q.empty() )
	{
		x = Q.top();  viz[x] = 0; Q.pop(); 
		for(i = 0; i < G[x].size(); ++i)
		{
			y = G[x][i];
			if( capac[x][y]!=0 && d[y] > d[x] + cst[x][y])
			{
				d[y] = d[x] + cst[x][y];
				tata[y] = x;
				if(viz[y]) continue;
				Q.push(y);
				viz[y] = 1;
			}
		}
			
	}
	if( d[D] == oo ) return 0;
	return 1;
}
void flux()
{
	int i;
	for(;BFS();)
	{
		for(i = D; i != S; i =tata[i])
		{
			capac[tata[i]][i] --;
			capac[i][tata[i]] ++;
		}
		CST += d[D];
	}
}
int pairUp(int x)
{
	if(viz[x]) return 0;
	int y; unsigned i;
	viz[x] = 1;
	for(i = 0; i < G[x].size(); ++i)
	{
		y = G[x][i];		
		if( !st[y] )
		{
			st[y] = x;
			dr[x] = y;
			return 1;
		}
	}
	for(i = 0; i < G[x].size(); ++i)
	{
		y = G[x][i];		
		if( pairUp(st[y]) )
		{
			st[y] = x;
			dr[x] = y;
			return 1;
		}
	}
	return 0;
}
void limiteaza(double L)
{
	int i, j;
	for(i = 1; i <= N; ++i)
	{
		G[i].clear();
		for(j = 1; j <= N; ++j)
			if( cin[i][j+N] <= L )
			{
				G[i].pb(j+N); G[j+N].pb(i);
				cst[i][j+N] = cin[i][j+N]; cst[j+N][i] = - cst[i][j+N];
				capac[i][j+N] = 1;
			}
		capac[S][i] = 1; G[S].pb(i); G[i].pb(S);
		capac[i+N][D] = 1; G[i+N].pb(D); G[D].pb(i+N);
	}
}
inline int pot(double lim)
{
	for(int i = 1; i <= N; ++i)
	{
		G[i].clear();
		for(int j = 1; j <= N; ++j)
			if(lim >= cin[i][j+N])
				G[i].push_back(j+N);
	}
	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 i, j;
	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;
		
		for(j = 1; j <= N; ++j)
		{
			d = dist(x, y, X[j], Y[j]);
			cin[i][j+N] = d;
			capac[i][j + N] = 1;			
			A[P++] = d;
		}
	}
	sort(A, A + P);
	int step;
	for(step=1; step<=P;step<<=1);
	for(i = P - 1; step; step>>=1)
		if( i - step >= 0 && pot( A[i - step] ) )
			i -= step;
	
	limiteaza(A[i]); CST = 0;
	flux();
	out<<setprecision(5)<<fixed<<A[i]<<" "<<CST<<"\n"; 	
	return 0;
}