Pagini recente » Cod sursa (job #2752734) | Cod sursa (job #2189771) | Cod sursa (job #934885) | Cod sursa (job #2144179) | Cod sursa (job #47668)
Cod sursa(job #47668)
#include <stdio.h>
#include <math.h>
#include <string.h>
#define NMAX 802
#define CMAX (1<<11)
#define INF 666000666
#define eps 0.000001
int F[NMAX][NMAX], InQ[NMAX], Q[CMAX], N;
double D[NMAX];
double C[NMAX][NMAX], Xs[NMAX], Ys[NMAX], Xa[NMAX], Ya[NMAX], Cm, Max;
int cup[NMAX];
void flux(int sursa, double crit)
{
int p1 = 0, p2 = 1, i, j, nod, tata[NMAX], tip[NMAX];
double min;
for (i = 0; i < NMAX; i++)
D[i] = INF, tata[i] = cup[i] = InQ[i] = tip[i] = 0;
for (i = 0; i < CMAX; i++) Q[i] = 0;
Q[p1] = sursa;
D[ sursa ] = 0;
InQ[ sursa ] = 1;
while (p1 != p2)
{
nod = Q[p1];
if (nod <= N)
{
for (i = N+1; i <= 2*N; i++)
if ((C[nod][i]-crit <= eps) && (F[nod][i] == 0) && (D[i]-D[nod]-C[nod][i]>eps))
{
D[i] = D[nod]+C[nod][i];
tata[i] = nod;
if (!InQ[i])
{
InQ[i] = 1;
Q[p2] = i;
p2 = (p2+1)&(CMAX-1);
}
}
}
else
{
if ((C[cup[nod]][nod]-crit <= eps) && (cup[nod] > 0) && (D[cup[nod]]-D[nod]+C[cup[nod]][nod]>eps))
{
D[cup[nod]] = D[nod]-C[cup[nod]][nod];
tata[cup[nod]] = nod;
tip[cup[nod]] = 1;
if (!InQ[cup[nod]])
{
InQ[cup[nod]] = 1;
Q[p2] = cup[nod];
p2 = (p2+1)&(CMAX-1);
}
}
}
InQ[nod] = 0;
p1 = (p1+1)&(CMAX-1);
}
j = 0;
min = INF;
for (i = N+1; i <= 2*N; i++)
if ((cup[i] == 0) && (min-D[i] > eps)) j = i, min = D[i];
Cm += min;
if (min < INF)
while (tata[j] > 0)
{
if (tip[j] == 0)
{
F[tata[j]][j]++;
cup[j] = tata[j];
}
else
F[j][tata[j]]--;
j = tata[j];
}
}
int main()
{
int i, j, nod;
double lo, hi, mid, max;
freopen("adapost.in", "r", stdin);
scanf("%d", &N);
for (i = 1; i <= N; i++)
scanf("%lf %lf", Xs+i, Ys+i);
for (i = 1; i <= N; i++)
scanf("%lf %lf", Xa+i, Ya+i);
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
{
C[i][N+j] = sqrt((Xa[j]-Xs[i])*(Xa[j]-Xs[i])+(Ya[j]-Ys[i])*(Ya[j]-Ys[i]));
if (C[i][N+j]-max >= eps) max = C[i][N+j];
}
lo = 0; hi = max;
while (hi-lo >= eps)
{
mid = (hi+lo)*0.5;
Cm = 0;
memset(F, 0, sizeof(F));
for (i = 1; i <= N && Cm < INF; i++) flux(i, mid);
if (Cm >= INF) lo = mid+eps;
else hi = mid-eps, Max = mid;
}
memset(F, 0, sizeof(F));
memset(cup, 0, sizeof(cup));
Cm = 0;
for (i = 1; i <= N; i++) flux(i, Max);
freopen("adapost.out", "w", stdout);
printf("%lf %lf\n", Max, Cm);
return 0;
}