Cod sursa(job #574421)

Utilizator loginLogin Iustin Anca login Data 7 aprilie 2011 10:31:40
Problema Adapost Scor 6
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
# include <fstream>
# include <iostream>
# include <algorithm>
# include <vector>
# include <queue>
# include <cmath>
# include <cassert>
# define INF 2000000000.
# define DIM 403
# define EPS 0.001
# define pb push_back
# define mp make_pair
# define fs first
# define sc second
using namespace std;
int n, N, c[2*DIM][2*DIM], t[2*DIM], v[2*DIM], a[2*DIM];
double b[2*DIM][2*DIM], d[2*DIM], dst[DIM*DIM], dist=INF, sum=INF;
vector< pair<double,double> >S, A;
queue<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(a,b));
	}
	for(int i=1;i<=n;++i)
	{
		fin>>a>>b;
		A.pb(mp(a,b));
	}
}

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

int g (double D)
{
	while (Q.size())Q.pop();
	for(int i=0;i<=N;++i)
		t[i]=-1, d[i]=INF, v[i]=0;
	d[0]=0;
	v[0]=1;
	Q.push(0);
	int i;
	while (Q.size())
	{
		i=Q.front();Q.pop();
		v[i]=0;
		for(int j=0;j<=N;++j)
			if (c[i][j]>0 && d[i]+b[i][j]<d[j])
			{
				d[j]=d[i]+b[i][j];
				t[j]=i;
				if (!v[j])
				{
					v[j]=1;
					Q.push(j);
				}
			}
	}
	if (d[N]<INF)return 1;
	return 0;
}

int ok (double D)
{
	for(int i=1;i<=n;++i)
	{
		c[0][i]=1;
		c[i][0]=0;
		c[n+i][N]=1;
		c[N][n+1]=0;
		for(int j=n+1;j<N;++j)
		{
			if (b[i][j]<=D)
				c[i][j]=1;
			else
				c[i][j]=0;
			c[j][i]=0;
		}
	}
	int fl=0;
	double dd=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;
		else if (D-dist<EPS && dist-D>-EPS && sum>dd)
			sum=dd;
		return 1;
	}
	return 0;
}
	

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

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