Cod sursa(job #574125)

Utilizator loginLogin Iustin Anca login Data 6 aprilie 2011 20:47:28
Problema Adapost Scor 6
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
# include <fstream>
# include <iostream>
# include <algorithm>
# include <vector>
# include <set>
# include <cmath>
# define INF 2000000000
# define DIM 403
# define pb push_back
# define mp make_pair
# define fs first
# define sc second
using namespace std;
int n, N, c[DIM][DIM], b[DIM][DIM], dist=INF, sum, dst[DIM*DIM], d[2*DIM], t[2*DIM], v[2*DIM];
vector< pair<int,int> >S, A;
set< pair<int,int> >Q;

void read ()
{
	ifstream fin ("adapost.in");
	fin>>n;
	N=2*n+1;
	double a, b;
	for(int i=1;i<=n;++i)
	{
		fin>>a>>b;
		S.pb(mp((int)(a*1000),(int)(b*1000)));
	}
	for(int i=1;i<=n;++i)
	{
		fin>>a>>b;
		A.pb(mp((int)(a*1000),(int)(b*1000)));
	}
}

int dstnt (int i, int j)
{
	long long x1, x2, y1, y2;
	x1=(long long)S[i].fs;
	x2=(long long)A[j].fs;
	y1=(long long)S[i].sc;
	y2=(long long)A[j].sc;
	return (int)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int g (int D)
{
	while (Q.size())Q.erase(Q.begin());
	for(int i=0;i<=N;++i)
		t[i]=-1, d[i]=INF, v[i]=0;
	d[0]=0;
	Q.insert(mp(0,0));
	int i, dd;
	while (Q.size())
	{
		i=(*Q.begin()).sc;
		dd=(*Q.begin()).fs;
		Q.erase(Q.begin());
		if (!v[i])
		{
			v[i]=1;
			if (i==N)return 1;
			for(int j=0;j<=N;++j)
				if (!v[j] && c[i][j]>0 && b[i][j]<=D && dd+b[i][j]<d[j])
				{
					d[j]=dd+b[i][j];
					t[j]=i;
					Q.insert(mp(d[j], j));
				}
			}
	}
	return 0;
}

int ok (int D)
{
	for(int i=1;i<=n;++i)
		for(int j=n+1;j<N;++j)
		{
			c[i][0]=c[j][i]=c[N][j]=0;
			c[0][i]=c[i][j]=c[j][N]=1;
		}
	int dd=0, fl=0;
	while (g(D))
	{
		++fl;
		dd+=d[N];
		for(int i=N;t[i]!=-1;i=t[i])
		{
			--c[t[i]][i];
			++c[i][t[i]];
		}
	}
	if (fl==n)
	{
		if (D<dist)
			dist=D, sum=dd;
		return 1;
	}
	return 0;
}
	

void cauta (int st, int dr)
{
	if (st==dr)
	{
		ok(dst[st]);
		return;
	}
	int mij=(st+dr)/2;
	if (ok(dst[mij]))
		cauta (st, mij);
	else
		cauta (mij+1, dr);
}

int main()
{
	read ();
	int d;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
		{
			d=dstnt(i,j);
			dst[++dst[0]]=d;
			b[i][n+j]=d;
			b[n+j][i]=-d;
		}
	sort(dst+1, dst+dst[0]+1);
	cauta (1, dst[0]);
	ofstream fout ("adapost.out");
	fout<<dist/1000.<<" "<<sum/1000.;
	return 0;
}