Pagini recente » Cod sursa (job #1888581) | Cod sursa (job #1239966) | Cod sursa (job #476616) | Cod sursa (job #2655396) | Cod sursa (job #77894)
Cod sursa(job #77894)
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
#define Nmax 404
int X1[Nmax], X2[Nmax], Y1[Nmax], Y2[Nmax], n;
int t[Nmax*2], q[Nmax*2];
int cost[Nmax*2][Nmax*2], c[Nmax*2][Nmax*2], f[Nmax*2][Nmax*2];
int h[Nmax*Nmax];
char viz[Nmax*2];
#define cf(i,j) (c[i][j] - f[i][j])
#define dist(a,c,b,d) sqrt((double)(a-b)*(a-b)+(c-d)*(c-d))
int BF()
{
int sus,jos,nod;
memset(viz,0,n*2 + 1);
jos = 0; sus = 1;
viz[0] = 1;
while (jos < jos)
{
nod = q[++jos];
for (int i=1;i<=n*2+1;++i)
if (cf(nod,i))
{
t[i] = nod;
viz[i] = 1;
q[++sus] = i;
}
}
return viz[n*2+1];
}
int solve(int distMax)
{
memset(f,0,sizeof(f));
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
if (cost[i][j+n] <= distMax)
c[i][j+n] = 1;
else
c[i][j+n] = 0;
for (int i=1;i<=n;++i) c[0][i] = 1;
for (int i=1;i<=n;++i) c[i+n][n*2+1] = 1;
int nr = 0;
while(BF())
{
int k;
++nr;
k = 2*n+1;
while (k)
{
++f[t[k]][k];
--f[k][t[k]];
k = t[k];
}
}
return nr == n;
}
int main()
{
freopen("adapost.in","r",stdin);
freopen("adapost.out","w",stdout);
double a,b;
scanf("%d",&n);
for (int i=1;i<=n;++i)
{
scanf("%lf%lf", &a,&b);
a *= 1000; b *= 1000;
a += 0.1; b += 0.1;
X1[i] = (int)a;
Y1[i] = (int)b;
}
for (int i=1;i<=n;++i)
{
scanf("%lf%lf", &a,&b);
a *= 1000; b *= 1000;
a += 0.1; b += 0.1;
X2[i] = (int)a;
Y2[i] = (int)b;
}
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
{
a = dist(X1[i]/1000,Y1[i]/1000,X2[j]/1000,Y2[j]/1000);
a *= 1000;
cost[i][j+n] = (int)a;
cost[j+n][i] = -cost[i][j+n];
h[(i-1)*n+j] = cost[i][j+n];
}
sort(h+1,h+(n*n+1));
int st,dr,mij=1;
st = 1;
dr = n*n;
while (st < dr)
{
mij = (st+dr)/2;
if (solve(h[mij]))
dr = mij;
else
st = mij + 1;
}
printf("%d.%.3u\n",h[mij]/1000,h[mij]%1000);
return 0;
}