Cod sursa(job #420198)

Utilizator FlorianFlorian Marcu Florian Data 18 martie 2010 17:26:01
Problema Adapost Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.84 kb
using namespace std;
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<queue>
#define pb push_back
#define EPS 1e-12
#define oo 0x3f3f3f3f
const int MAX_N = 804;
double cst[MAX_N][MAX_N], cin[MAX_N][MAX_N];
short int capac[MAX_N][MAX_N];
int N,P, S, D;
bool viz[MAX_N];
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];
struct cmp2 
{ 
	bool operator()(const int &a, const int &b) 
	{ 
		int r = comp(d[a],d[b]);
		if( r == -1) return 1;
		return 0;		
	} 
};
double SUM;
int belman()
{
	int x, y, i;
	for(i = 1; i <= D; ++i) d[i] = oo, viz[i] = false, tata[i] = 0;
	queue<int>Q;
	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);
			}
		}
	}
	SUM = d[D];
	if( d[D] == oo ) return 0;
	return 1;
}
int dijkstra()
{
	int x, y, i;
	priority_queue <int, vector <int>, cmp2 > Q; 
	for(x = S; x <= D; ++x)
		for(y = S; y <= D; ++y)
			if( d[y] != oo && d[x] != oo)
				cst[x][y] += d[x] - d[y];
			
	for(i = 1; i <= D; ++i) d[i] = oo, tata[i] = 0;
	d[S] = 0;
	for( Q.push(S); !Q.empty(); Q.pop() )
	{
		x = Q.top(); 
		for(y = S; y <= D; ++y)
			if( capac[x][y] && comp(cin[x][y] , LIM) != -1 && comp(d[y] , d[x] + cst[x][y]) == -1 )
			{
				d[y] = d[x] + cst[x][y];
				tata[y] = x;
				Q.push(y);
			}
	}
	SUM += d[D];
	if( d[D] == oo ) return 0;
	return 1;
}
void flux()
{
	int i, f;
	for(;dijkstra();)
	{
		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 * SUM;
	}
}
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;
			cin[i][j+N] = d; cin[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 ) 
		{ 
			belman();
			flux();
			out<<setprecision(5)<<fixed<<A[m]<<" "<<CST<<"\n"; 
			return 0; }
		else if( r && p ) dr = m - 1;
		else st = m + 1;
	}
	return 0;
}