Cod sursa(job #518221)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 30 decembrie 2010 19:30:53
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

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

#define nmax 410

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

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;
}

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;
}
	



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);
	
	
	return 0;
	
}