Cod sursa(job #77892)

Utilizator crawlerPuni Andrei Paul crawler Data 15 august 2007 01:04:04
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

#define Nmax 404

int X1[Nmax], X2[Nmax], Y1[Nmax], Y2[Nmax], n;
int t[Nmax*2], q[Nmax*2];
int cost[Nmax*2][Nmax*2], c[Nmax*2][Nmax*2], f[Nmax*2][Nmax*2];
int h[Nmax*Nmax];
char viz[Nmax*2];

#define cf(i,j) (c[i][j] - f[i][j])
#define dist(a,c,b,d) sqrt((double)(a-b)*(a-b)+(c-d)*(c-d))

int BF()
{
	int sus,jos,nod;	
	memset(viz,0,n*2 + 1);

	jos = 0; sus = 1;
	viz[0] = 1;
	while (jos < jos)
	{
		nod = q[++jos];

		for (int i=1;i<=n*2+1;++i)
		if (cf(nod,i))
		{
			t[i] = nod;
			viz[i] = 1;
			q[++sus] = i;
		}	
	}		
	return viz[n*2+1];
}

int solve(int distMax)
{
	memset(f,0,sizeof(f));
    
    for (int i=1;i<=n;++i)
	for (int j=1;j<=n;++j)
	if (cost[i][j+n] <= distMax)
		c[i][j+n] = 1;
			else
		c[i][j+n] = 0;
	for (int i=1;i<=n;++i)	c[0][i] = 1;
	for (int i=1;i<=n;++i)	c[i+n][n*2+1] = 1;

	while(BF())
	{
		int k;
		k = 2*n+1;
		while (k)
		{
			++f[t[k]][k];
			--f[k][t[k]];
			k = t[k];
		}		
	}
}

int main()
{
	freopen("adapost.in","r",stdin);
	freopen("adapost.out","w",stdout);

	double a,b;

	scanf("%d",&n);

	for (int i=1;i<=n;++i)
	{
		scanf("%lf%lf", &a,&b);
		a *= 1000; b *= 1000;	
		X1[i] = (int)a;
		Y1[i] = (int)b;
		//printf("%d.%d %d.%d\n",X1[i]/1000,X1[i]%1000,Y1[i]/1000,Y1[i]%1000);
		printf("%.3f %.3f\n",a,b);
	}

	for (int i=1;i<=n;++i)
	{
		scanf("%lf%lf", &a,&b);
		a *= 1000; b *= 1000;
		X2[i] = (int)a;
		Y2[i] = (int)b;
	}

	for (int i=1;i<=n;++i)
	for (int j=1;j<=n;++j)
	{
		a = dist(X1[i]/1000,Y1[i]/1000,X2[j]/1000,Y2[j]/1000);
		a *= 1000;
		cost[i][j+n] = (int)a;
		cost[j+n][i] = -cost[i][j+n];
		h[(i-1)*n+j] = cost[i][j+n];
		printf("%d %d -> %d %d  == %.3f\n",X1[i],Y1[i],X2[j],Y2[j],a);
	}

	sort(h+1,h+(n*n+1));
	
	int st,dr,mij=1;
	st = 1;
	dr = n*n;
	
	while (st < dr)
	{
		mij = (st+dr)/2;
		if (solve(h[mij])) 
		dr = mij;
			else
		st = mij + 1;
	}

	printf("%d.%d\n",h[mij]/1000,h[mij]%1000);

	return 0;
}