Cod sursa(job #518272)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 30 decembrie 2010 22:49:12
Problema Adapost Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.92 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

#define file_in "adapost.in"
#define file_out "adapost.out"

#define nmax 1010

int l[nmax*nmax];
int r[nmax*nmax];
int viz[nmax*nmax];
vector<int> G[nmax*nmax];
vector<pair<int,double > > g[nmax*nmax];
struct pozitie{
	int i,j;
	double d;
}p[nmax*nmax];
struct q{
double x,y;
}a[nmax*nmax],b[nmax*nmax];
int N,nr,dest,x,y,tata[nmax*nmax];
int C[nmax][nmax];
int F[nmax][nmax];
double cost[nmax*nmax];

double dist(double x1, double y1, double x2, double y2){
	
	return sqrt((y1-y2)*(y1-y2)+(x1-x2)*(x1-x2));
}

int cmp(pozitie a, pozitie b){
	
	return a.d<b.d;
}

struct comp
{
	bool operator()(int i,int j)
	{
		return cost[i]>cost[j];
	}
};
priority_queue<int,vector<int>,comp> q;



int cupleaza(int nod)
{
    if (viz[nod])
         return 0;
     viz[nod]=1;

     vector<int> :: iterator it;

     for (it=G[nod].begin();it!=G[nod].end();++it)
          if (!r[*it])
          {
              l[nod]=(*it);
              r[*it]=nod;
              return 1;
          }
      for (it=G[nod].begin();it!=G[nod].end();++it)
          if (cupleaza(r[*it]))
          {
              l[nod]=(*it);
              r[*it]=nod;
              return 1;
          }

          return 0;

}

void constr_graf(double nod){
	
	int i;
	
	for (i=1;i<=N;++i){
		 G[i].clear();
		 l[i]=r[i]=0;
	}
	
	for (i=1;i<=nr && p[i].d<=nod;++i)
		 G[p[i].i].push_back(p[i].j);
}



int bun(double nod){
	
	int ok,ans,i;
	
	constr_graf(nod);
	
	ok=1;
    ans=0;	
	
    while(ok)
    {
        memset(viz,0,sizeof(viz));
        ok=0;
        for (i=1;i<=N;++i)
             if (!l[i] && cupleaza(i))
             {
					 ans++;
                     ok=1;
			 }
    }

	if (ans!=N) 
        return 0;
	
	return 1;
}

#define inf 0x3f3f3f3f
	
int dijkstra()
{
    vector<pair <int,double> >:: iterator it;
	int i,nod;
	for(i=1;i<=dest;++i) cost[i]=inf;
	q.push(0);
	cost[0]=0;
	while(!q.empty())
	{
		nod=q.top();
		viz[nod]=0;
		q.pop();
		for(it=g[nod].begin();it!=g[nod].end();++it)
			if(C[nod][(it->first)]-F[nod][(it->first)]>0 && cost[(it->first)]>cost[nod]+(it->second))
			{
				cost[(it->first)]=cost[nod]+(it->second);
                tata[(it->first)]=nod;
				if(viz[(it->first)]!=1){
					q.push(it->first);
					viz[it->first]=1;
				}
			}
	}
	if(cost[dest]<inf)
        return 1;
    return 0;
}



int main(){
	
	int i,j,ls,ld,mij;
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &N);
	for (i=1;i<=N;++i)
		 scanf("%lf %lf", &a[i].x, &a[i].y);
	for (i=1;i<=N;++i)
		 scanf("%lf %lf", &b[i].x, &b[i].y);
	
	nr=0;
	for (i=1;i<=N;++i)
		 for (j=1;j<=N;++j){
			  
			  p[++nr].d=dist(a[i].x,a[i].y,b[j].x,b[j].y); 
			  p[nr].i=i;
			  p[nr].j=j;
		 }
	sort(p+1,p+nr+1,cmp);


	ls=1,ld=nr;
    while(ls<=ld)
    {
        int mij=(ls+ld)/2;
        if(bun(p[mij].d))
            ld=mij-1;
        else 
			ls=mij+1;
    }

	
	//for (i=1;i<=nr;++i)
	//	 printf("%lf\n", p[i].d);
	//printf("%d %d %d\n", ls,ld,mij);
	printf("%.5lf ", p[ls].d);
	
	dest=2*N+1;
	for (i=1;i<=nr && p[i].d<=p[ls].d;++i){
		
		x=p[i].i;
		y=p[i].j+N;
	    C[x][y]=C[0][x]=C[y][dest]=1;
		g[x].push_back(make_pair(y,p[i].d));
		g[y].push_back(make_pair(x,-p[i].d));
		g[x].push_back(make_pair(0,0));
		g[0].push_back(make_pair(x,0));
		g[y].push_back(make_pair(dest,0));
		g[dest].push_back(make_pair(y,0));
	}
	
	double sol=0;
    while(dijkstra())
    {
        int Vmin=inf;
        for(i=dest;i!=0;i=tata[i])
            Vmin=min(Vmin,C[tata[i]][i]-F[tata[i]][i]);
        for(i=dest;i!=0;i=tata[i])
        {
            F[tata[i]][i]+=Vmin;
            F[i][tata[i]]-=Vmin;
        }
        if(Vmin)
           sol+=cost[dest];
	}
    printf("%.5lf\n",sol);

	
	return 0;
	
}