Cod sursa(job #402615)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 23 februarie 2010 23:43:49
Problema Adapost Scor 6
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

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

#define Nmax 1044

vector<int> G[Nmax];
int viz[Nmax];
int cuplaj1[Nmax];
int cuplaj2[Nmax];
struct ad
{
	int x,y;
	double c;
}
v[Nmax];
int nr,n;
double a1[Nmax],b2[Nmax];
double a2[Nmax],b1[Nmax];

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

int cmp(ad a, ad b)
{
	return (a.c<b.c);
}

int cuplaj(int nod)
{
	int x;
	if (viz[nod]==1)
		return 0;
	
	viz[nod]=1;
	
	for (int i=0;i<G[nod].size();++i)
	{
		x=G[nod][i];
		if (cuplaj1[x]==0)
		{
			cuplaj2[nod]=1;
			cuplaj1[x]=nod;
			return 1;
		}
	}
	
	for (int i=0;i<G[nod].size();++i)
	{
		x=G[nod][i];
		if (cuplaj1[x]!=nod && cuplaj(cuplaj1[x]))
		{
			cuplaj2[nod]=1;
			cuplaj1[x]=nod;
			return 1;
		}
	}
	
	return 0;
}


int good(double nod)
{
	int i,ok,nrr;
	for (i=1;i<=nr;++i)
		 G[i].clear();
	memset(cuplaj1,0,sizeof(cuplaj1));
	memset(cuplaj2,0,sizeof(cuplaj2));
	
	//contruieste noul graf
	
	for (i=1;i<=nr && v[i].c<=nod;++i)
		 G[v[i].x].push_back(v[i].y);
	
	nrr=0;
	///baga cuplaj
	ok=1;
	while(ok)
	{
		ok=0;
		memset(viz,0,sizeof(viz));
		for (i=1;i<=n;++i)
			 if (cuplaj2[i]==0 && cuplaj(i))
			 {
				 nrr++;
				 ok=1;
			 }
	}
	
	return (n==nrr);
}

int main()
{
	int i,ls,ld,sol,mij,j;
    double d;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	for (i=1;i<=n;++i)
		scanf("%lf %lf", &a1[i], &b1[i]); 
	for (i=1;i<=n;++i)
		scanf("%lf %lf", &a2[i], &b2[i]); 
    
	//formez distantele
	nr=0;
	for (i=1;i<=n;++i)
		 for (j=1;j<=n;++j)
		 {
			 d=dist(a1[i],b1[i],a2[j],b2[j]);
			 v[++nr].c=d;
			 v[nr].x=i;
			 v[nr].y=j;
		 }
	
		 
	//sorteaza in functie de distanta
     sort(v+1,v+nr+1,cmp);		 
	 
	 /*for (i=1;i<=nr;++i)
         printf("%.5lf\n", v[i].c);	*/
	//cautare binara intervalu [1,nr]	
    ls=1;
    ld=nr;
    while(ls<=ld)
	{
		mij=(ls+ld)>>1;
		
		if (good(v[mij].c))
		{
			sol=mij;
			ld=mij-1;
		}
		else
		{
			ls=mij+1;
		}
	}

	printf("%.5lf ", v[sol].c);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}