Cod sursa(job #323633)

Utilizator AndreyPAndrei Poenaru AndreyP Data 12 iunie 2009 22:51:44
Problema Adapost Scor 97
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.56 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
#define N 410
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
short n,sursa,dest;
bitset<N> viz;
const double eps=0.001;
double a[N][N],d[N<<1];
char c[N<<1][N<<1],f[N<<1][N<<1];
short ref[N][N],cine,l[N],r[N],nh,h[N<<1],inheap[N<<1],t[N<<1];
double caut[N*N],ka;
const double inf=100010;
vector< pair<short,double> > b[N<<1];
int cc;
inline double dist(pair<double,double> &x,pair<double,double> &y)
{
	return sqrt((x.fs-y.fs)*(x.fs-y.fs)+(x.sc-y.sc)*(x.sc-y.sc));
}
inline char cmp(double x,double y)
{
	if(x+eps<y)
		return -1;
	if(y+eps<x)
		return 1;
	return 0;
}
bool compar(const short &x,const short &y)
{
	if(cmp(a[cine][x],a[cine][y])==-1)
		return true;
	return false;
}
inline void citire()
{
	scanf("%hd",&n);
	pair<double,double> v[N];
	pair<double,double> now;
	for(short i=1; i<=n; ++i)
		scanf("%lf%lf",&v[i].fs,&v[i].sc);
	for(short i=1; i<=n; ++i)
	{
		scanf("%lf%lf",&now.fs,&now.sc);
		for(short j=1; j<=n; ++j)
		{
			double aux=dist(v[j],now);
			caut[++cc]=aux;
			a[j][i]=aux;
			ref[j][i]=i;
		}
	}
	for(short i=1; i<=n; ++i)
	{
		cine=i;
		sort(ref[i]+1,ref[i]+n+1,compar);
	}
}
inline bool pairup(short nod)
{
	if(viz[nod])
		return false;
	viz[nod]=1;
	for(short i=1; i<=n && cmp(a[nod][ref[nod][i]],ka)!=1; ++i)
	{
		short nod1=ref[nod][i];
		if(!l[nod1])
		{
			l[nod1]=nod;
			r[nod]=nod1;
			return true;
		}
	}
	for(short i=1; i<=n && cmp(a[nod][ref[nod][i]],ka)!=1; ++i)
	{
		short nod1=ref[nod][i];
		if(pairup(l[nod1]))
		{
			l[nod1]=nod;
			r[nod]=nod1;
			return true;
		}
	}
	return false;
}
inline bool vezi()
{
	memset(l,0,sizeof(l));
	memset(r,0,sizeof(r));
	bool change=true;
	while(change)
	{
		change=false;
		viz.reset();
		for(int i=1; i<=n; ++i)
		{
			if(!r[i])
				change|=pairup(i);
		}
	}
	for(int i=1; i<=n; ++i)
	{
		if(!r[i])
			return false;
	}
	return true;
}
bool compar1(const double &x,const double &y)
{
	if(cmp(x,y)==-1)
		return true;
	return false;
}
inline short left_son(short x)
{
	return x<<1;
}
inline short right_son(short x)
{
	return (x<<1)+1;
}
inline short father(short x)
{
	return x>>1;
}
inline void upheap(short k)
{
	short key=h[k];
	while(k>1 && cmp(d[key],d[h[father(k)]])==-1)
	{
		h[k]=h[father(k)];
		inheap[h[k]]=k;
		k=father(k);
	}
	h[k]=key;
	inheap[h[k]]=k;
}
inline void downheap(short k)
{
	short son;
	do
	{
		son=0;
		if(left_son(k)<=nh)
		{
			son=left_son(k);
			if(right_son(k)<=nh && cmp(d[right_son(k)],d[h[son]])==-1)
				son=right_son(k);
			if(cmp(d[h[k]],d[h[son]])!=1)
				son=0;
		}
		if(son)
		{
			swap(h[k],h[son]);
			inheap[h[k]]=k;
			inheap[h[son]]=son;
			k=son;
		}
	}while(son);
}
inline void precalc()
{	
	sursa=(n<<1)+1;
	dest=(n<<1)+2;
	b[n+1].reserve(dest);
	b[n+2].reserve(dest);
	for(short i=1; i<=n; ++i)
	{
		for(short j=1; j<=n; ++j)
		{
			if(cmp(a[i][j],ka)==1)
				continue;
			b[i].pb(mp(j+n,a[i][j]));
			c[i][j+n]=1;
			b[j+n].pb(mp(i,-a[i][j]));
		}
		b[sursa].pb(mp(i,0));
		c[sursa][i]=1;
		b[i].pb(mp(sursa,0));
		b[i+n].pb(mp(dest,0));
		c[i+n][dest]=1;
		b[dest].pb(mp(i+n,0));
	}
}
inline bool dijkstra()
{
	for(short i=1; i<=dest; ++i)
	{
		d[i]=inf;
		inheap[i]=0;
		t[i]=0;
	}
	nh=1;
	h[1]=sursa;
	inheap[sursa]=1;
	d[sursa]=0;
	short now,next;
	double cost;
	while(nh)
	{
		now=h[1];
		inheap[now]=0;
		h[1]=h[nh--];
		inheap[h[1]]=1;
		downheap(1);
		for(int i=0,lim=b[now].size(); i<lim; ++i)
		{
			next=b[now][i].fs;
			cost=b[now][i].sc;
			if(c[now][next]==f[now][next] || cmp(d[next],d[now]+cost)!=1)
				continue;
			d[next]=d[now]+cost;
			t[next]=now;
			if(inheap[next])
				upheap(inheap[next]);
			else
			{
				h[++nh]=next;
				inheap[h[nh]]=nh;
				upheap(nh);
			}
		}
	}
	if(d[dest]==inf)
		return false;
	return true;
}
inline void flux()
{
	double sol=0;
	while(dijkstra())
	{
		short aux=dest;
		while(aux!=sursa)
		{
			++f[t[aux]][aux];
			--f[aux][t[aux]];
			aux=t[aux];
		}
		sol+=d[dest];
	}
	printf("%lf\n",sol);
}
int main()
{
	freopen("adapost.in","r",stdin);
	freopen("adapost.out","w",stdout);
	citire();
	sort(caut+1,caut+cc+1,compar1);
	int p=1,u=cc;
	while(p<u)
	{
		int mij=(p+u)>>1;
		ka=caut[mij];
		if(vezi())
			u=mij;
		else
			p=mij+1;
	}
	ka=caut[p];
	printf("%lf ",caut[p]);
	if(caut[p]==0)
		exit(4);
	precalc();
	flux();
	return 0;
}