Pagini recente » Cod sursa (job #1537627) | Cod sursa (job #2465688) | Cod sursa (job #2279850) | Cod sursa (job #1426437) | Cod sursa (job #402341)
Cod sursa(job #402341)
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#define Nmx 405
#define INF 1000001
using namespace std;
struct coord{ double x,y;};
int n,nr,Q[Nmx*Nmx*10],st,dr,viz[Nmx*2],prec[Nmx*2];
int C[Nmx*2][Nmx*2],F[Nmx*2][Nmx*2],r[Nmx*2],l[Nmx*2];
coord a[Nmx],b[Nmx];
vector<int> g[Nmx];
struct date{
int x1,x2;
double d;
}c[Nmx];
double dist(double x,double y,double x1,double y1)
{
return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}
bool cmp(const date &a,const date &b)
{
return a.d<b.d;
}
void citire()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lf%lf",&a[i].x,&a[i].y);
for(int i=1;i<=n;++i)
scanf("%lf%lf",&b[i].x,&b[i].y);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
c[++nr].d=dist(a[i].x,a[i].y,b[j].x,b[j].y);
c[nr].x1=i;c[nr].x2=j;
}
sort(c+1,c+nr+1,cmp);
}
int pairup (int nod)
{
int i;
if (viz[nod])
return 0;
viz[nod]=1;
for (i=0; i<(int)g[nod].size (); ++i)
if (!r[g[nod][i]])
{
r[g[nod][i]]=nod;
l[nod]=g[nod][i];
return 1;
}
for (i=0; i<(int)g[nod].size (); ++i)
if (pairup (r[g[nod][i]]))
{
l[nod]=g[nod][i];
r[g[nod][i]]=nod;
return 1;
}
return 0;
}
void build_graph(double x)
{
for(int i=1;i<=n;++i)
{
g[i].clear();
l[i]=0;
r[i]=0;
}
for(int i=1;i<=nr&&c[i].d<=x;++i)
g[c[i].x1].push_back(c[i].x2);
}
int este(double x)
{
build_graph(x);
int i,ok,cupl=0;
do
{
ok=0;
memset(viz,0,sizeof (viz));
for (i=1; i<=n; ++i)
if (!l[i] && pairup (i))
{
++cupl;
ok=1;
}
}
while (ok);
if(cupl!=n)
return 0;
return 1;
}
void solve()
{
int st=1,dr=nr;
while(st<=dr)
{
int mij=(st+dr)/2;
if(este(c[mij].d))
dr=mij-1;
else st=mij+1;
}
printf("%lf ",c[st].d);
}
int main()
{
freopen("adapost.in","r",stdin);
freopen("adapost.out","w",stdout);
citire();
solve();
return 0;
}