Cod sursa(job #574581)

Utilizator bora_marianBora marian bora_marian Data 7 aprilie 2011 12:10:51
Problema Adapost Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include<fstream>
#include<iostream>
#include<queue>
#include<cmath>
#define DIM 413
#define INF 2147000000
using namespace std;
struct point{
	long long x,y;};
point ad[DIM],v[DIM];
int c[2*DIM][2*DIM],d[DIM][DIM],t[2*DIM],viz[2*DIM],f[2*DIM][2*DIM],n,minim=INF;
queue<int>Q;
int bfs();
void solve(int st,int dr);
int dist(point a,point b);
int verifica(int val);
int main()
{
	ifstream fin("adapost.in");
	freopen("adapost.out","w",stdout);
	fin>>n;
	int i,j;
	double a,b;
	for(i=1;i<=n;i++)
	   fin>>a>>b,v[i].x=10000*a,v[i].y=10000*b;
	for(i=1;i<=n;i++)
	   fin>>a>>b,ad[i].x=10000*a,ad[i].y=10000*b;
	for(i=1;i<=n;i++)
	   for(j=1;j<=n;j++)
	       d[i][j]=dist(v[i],ad[j]);
	solve(1,2000000000);
	a=minim/10000.;
	printf("%.3lf 0",a);
	return 0;
}
int dist(point a,point b)
{
	return sqrt((long long)(a.x-b.x)*(a.x-b.x)+(long long)(a.y-b.y)*(a.y-b.y));
}
void solve(int st,int dr)
{
	if(st==dr)
	{
		if(verifica(st)==1 && st<minim)
		  minim=st;
		 return ;
	 }
	 int mij=(st+dr)/2;
	 if(verifica(mij)==1)
	 {
		 if(mij<minim)
		   minim=mij;
		 solve(st,mij);
	 }
	 else
	    solve(mij+1,dr);
}
int verifica(int val)
{
	int i,j,rez=0;
	for(i=1;i<=n;i++)
	   for(j=1;j<=n;j++)
	   {
		   c[i][j+n]=0;
		   f[i][j+n]=0,f[j+n][1]=0;
		   if(d[i][j]<=val)
		     c[i][j+n]=1;
		 }
	for(i=1;i<=n;i++)
	   c[0][i]=1,c[i+n][2*n+1]=1,f[0][i]=0,f[i][0]=0,f[i+n][2*n+1]=f[2*n+1][i+n]=0;
	while(bfs()==1)
	{
		rez++;
		 for(i=2*n+1;t[i]>=0;i=t[i])
		    f[t[i]][i]++,
		    f[i][t[i]]--;
	}
	if(rez==n)
	  return 1;
	else
	  return 0;
}
int bfs()
{
	while(Q.size())
	   Q.pop();
	Q.push(0);
	int i;
	for(i=1;i<=2*n+1;i++)
	   t[i]=-1,viz[i]=0;
	t[0]=-1;
	viz[0]=1;   
	while(Q.size())
	{
		int k=Q.front();
		Q.pop();
		for(i=1;i<=2*n+1;i++)
		   if(viz[i]==0 && c[k][i]>f[k][i])
		   {
			   viz[i]=1;
			   t[i]=k;
			   Q.push(i);
			   if(i==2*n+1)
			     return 1;
			 }
		}
		return 0;
}