Cod sursa(job #319852)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 2 iunie 2009 13:37:57
Problema Adapost Scor 38
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.9 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <algorithm>

#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair

#define IN  "adapost.in"
#define OUT "adapost.out"
#define N_MAX 1<<9

typedef vector<int> VI;
typedef pair<int,int> pi;
typedef vector<string> VS;

vector<pi> Q1(N_MAX),Q2(N_MAX);
VI A[1<<10];
int S,E,N,T[1<<10],L[N_MAX],R[N_MAX];
ll D[1<<10][1<<10],C[1<<10][1<<10];;
ll Q[1<<18],Dist[1<<10];
bool viz[1<<10];

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d",&N);
	
	double x,y;
	
	FOR(i,1,N)
	{
		scanf("%lf%lf\n",&x,&y);
		x *= 1000;y *= 1000;
		Q1[i] = mp( (int)x, (int)y);
	}	
	
	FOR(i,1,N)
	{
		scanf("%lf%lf\n",&x,&y);
		x *= 1000;y *= 1000;
		Q2[i] = mp( (int)x, (int)y);
	}	
}

II ll dist(pi x,pi y)
{
	return 1LL * (x.f - y.f) * (x.f - y.f) + 1LL * (x.s - y.s) * (x.s - y.s);
}

II bool DF(int nod)
{
	if(viz[nod])
		return false;
	viz[nod] = true;
	
	for(VI::iterator it=A[nod].begin();it != A[nod].end();++it)
		if(!L[*it])
		{
			L[*it] = nod;
			R[nod] = *it;
			return true;
		}	
	
	for(VI::iterator it=A[nod].begin();it != A[nod].end();++it)
		if(DF( L[*it] ) )
		{
			L[*it] = nod;
			R[nod] = *it;
			return true;
		}	
	return false;	
}

II bool cuplaj(ll dist)
{
	CC(L),CC(R);
	
	FOR(i,1,N)
	{
		A[i].resize(0);
		FOR(j,1,N)
			if(D[i][j] <= dist)
				A[i].pb(j);
	}
	
	bool ok(true);
	
	for(;ok;)
	{
		ok = false;
		CC(viz);
		FOR(i,1,N)
			if(!R[i])
				ok |= DF(i);
	}
	
	int rez(0);
	FOR(i,1,N)
		if(R[i])
			++rez;
	return rez == N;	
}

struct comp{ bool operator() (int i,int j) {return Dist[i] > Dist[j];}  };
priority_queue<int,VI,comp> Qh;

II bool Dijkastra()
{
	memset(Dist,100,sizeof(Dist) );
	int G[1<<10]={0};
	CC(T);
	Dist[S] = 0;
	Qh.push(S);
	++G[S];
	
	for(int nod;!Qh.empty();)
	{
		nod = Qh.top();
		--G[nod];
		Qh.pop();
		if(G[nod])
			continue;
		
		for(VI::iterator it=A[nod].begin();it != A[nod].end();++it)
			if(C[nod][*it] && Dist[*it] > Dist[nod] + D[nod][*it])
			{
				Dist[*it] = Dist[nod] + D[nod][*it];
				T[*it] = nod;
				
				Qh.push(*it);
				++G[*it];
			}	
	}	
	return T[E];
}

II db distf(ll dist)
{
	db aux = (db)dist / (db)1000000;
	return sqrt(aux);
}

II void flow()
{
	S = N+N+1;
	E = N+N+2;
	
	FOR(i,1,N)
	{
		A[S].pb(i);
		A[i].pb(S);
		A[E].pb(i+N);
		A[i+N].pb(E);
		
		C[S][i] = 1,
		C[i+N][E] = 1;
	}
	
	db rez(0);
	
	for(Dijkastra();Dijkastra();)
	for(int nod = E;T[nod];--C[ T[nod] ][nod],++C[nod][ T[nod] ],rez += distf(D[ T[nod] ][nod]),nod = T[nod]);
	
	printf("%lf\n",rez);
}

/*
II db afis(ll dist)
{
	db rez = (db) dist / 1000000;	
	return sqrt(rez);
}
*/

II void solve()
{
	Q[0] = 0;
	
	FOR(i,1,N)
	FOR(j,1,N)
		Q[++Q[0]] = D[i][j] = dist(Q1[i],Q2[j]);
	sort(Q+1,Q+Q[0]+1);
	
	int aux = Q[0];
	Q[0] = 0;
	FOR(i,1,aux)
		if(i==1 || Q[i] != Q[i-1])
			Q[++Q[0]] = Q[i];
	
//	FOR(i,1,Q[0])
//		printf("%lf\n",afis(Q[i]) );	

	int m,step;
	for(step = 1;step <= Q[0];step <<= 1);
	for(m=1;step;step >>= 1)
		if(m + step <= Q[0] && !cuplaj(Q[m+step-1]) ) 
			m += step;
	
	db rez = (db)Q[m] / (db)1000000;
	printf("%lf ",sqrt(rez));
	
	FOR(i,1,N)
		A[i].resize(0);
	FOR(i,1,N)
	FOR(j,1,N)
		if(D[i][j] <= Q[m])
		{
			A[i].pb(i + N);
			A[i + N].pb(j);
			D[i][i+N] = D[i][j];
			D[i+N][i] = -D[i][j];
			C[i][i+N] = 1;
		}	
	
	flow();
}

int main()
{
	scan();
	solve();
	return 0;
}