Cod sursa(job #577096)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 9 aprilie 2011 18:53:27
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.28 kb
#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>
#include <math.h>
#define NMAX 405
#define LMAX 811
#define prec 0.001
#define INF 100000000
#define pb push_back
using namespace std;
struct punct{double x,y;};
punct A[NMAX],B[NMAX];
int n,st[NMAX],dr[NMAX],sursa,dest,E[LMAX][LMAX],F[LMAX][LMAX],dad[LMAX];
double C[NMAX][NMAX],rez1,rez2,dist[LMAX];
vector <int> D[LMAX];
vector <double> G[LMAX];
queue <int> Q;
char marc[NMAX],in[LMAX],still;
double d_pcte(punct a,punct b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void read()
{
	scanf("%d",&n);
	int i,j;
	for (i=1; i<=n; i++)
		scanf("%lf%lf",&A[i].x,&A[i].y);
	for (i=1; i<=n; i++)
		scanf("%lf%lf",&B[i].x,&B[i].y);
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			C[i][j]=d_pcte(A[i],B[j]);
}
void sterge()
{
	int i;
	for (i=1; i<=n; i++)
		D[i].clear();
	memset(st,0,sizeof(st));
	memset(dr,0,sizeof(dr));
}
void construct(double val)
{
	sterge();
	int i,j;
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			if (C[i][j]<val)
				D[i].pb(j);
}
int pairup(int nod)
{
	marc[nod]=1;
	int i,vec;
	for (i=0; i<D[nod].size(); i++)
	{
		vec=D[nod][i];
		if (!dr[vec])
		{
			st[nod]=vec; dr[vec]=nod;
			return 1;
		}
	}
	for (i=0; i<D[nod].size(); i++)
	{
		vec=D[nod][i];
		if (!marc[dr[vec]] && pairup(dr[vec]))
		{
			st[nod]=vec; dr[vec]=nod;
			return 1;
		}
	}
	return 0;
}
inline int ok(double val)
{
	construct(val);
	int i,fin=1,act=0;
	while (fin)
	{
		fin=0;
		memset(marc,0,sizeof(marc));
		for (i=1; i<=n; i++)
			if (!st[i])
				if (pairup(i))
				{
					act++;
					fin=1;
				}
	}
	return act==n;
}
double cbin()
{
	double st=0,dr=20000,mij;
	while (dr-st>prec)
	{
		mij=(st+dr)/2;
		if (ok(mij))
			dr=mij;
		else
			st=mij;
	}
	return st;
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
double bford()
{
	int i,nod,vec;
	for (i=1; i<=dest; i++)
		dist[i]=INF;
	Q.push(sursa); in[sursa]=1;
	while (!Q.empty())
	{
		nod=Q.front();
		Q.pop();
		in[nod]=0;
		for (i=0; i<D[nod].size(); i++)
		{
			vec=D[nod][i];
			if (E[nod][vec]-F[nod][vec]>0 && dist[vec]>dist[nod]+G[nod][i])
			{
				dad[vec]=nod;
				dist[vec]=dist[nod]+G[nod][i];
				if (!in[vec] && vec!=dest)
					Q.push(vec),in[vec]=1;
			}
		}
	}
	if (dist[dest]!=INF)
	{
		still=1;
		int val=INF;
		for (i=dest; i!=sursa; i=dad[i])
			val=min(val,E[dad[i]][i]-F[dad[i]][i]);
		for (i=dest; i!=sursa; i=dad[i])
		{
			F[dad[i]][i]+=val;
			F[i][dad[i]]-=val;
		}
		return val*dist[dest];
	}
	return 0;
}
void fa_graf()
{
	int i,j;
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			if (C[i][j]<rez1+prec)
			{
				E[i][j+n]=1;
				D[i].pb(j+n); G[i].pb(C[i][j]);
				D[j+n].pb(i); G[j+n].pb(-C[i][j]);
			}
	sursa=0; dest=2*n+1;
	for (i=1; i<=n; i++)
	{
		E[sursa][i]=1; 
		D[sursa].pb(i);  G[sursa].pb(0); D[i].pb(sursa); G[i].pb(0); 
		E[i+n][dest]=1;
		D[i+n].pb(dest); G[i+n].pb(0); D[dest].pb(i+n);  G[dest].pb(0);
	}
}
void solve()
{
	sterge();
	fa_graf();
	still=1;
	while (still)
	{
		still=0;
		rez2+=bford();
	}
}
int main()
{
	freopen("adapost.in","r",stdin);
	freopen("adapost.out","w",stdout);
	read();
	rez1=cbin();
	printf("%lf ",rez1);
	//solve();
	printf("%lf\n",rez2);
	return 0;
}