Pagini recente » Cod sursa (job #2558334) | Cod sursa (job #2533822) | Cod sursa (job #1169453) | Cod sursa (job #1646793) | Cod sursa (job #518221)
Cod sursa(job #518221)
#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;
}