Cod sursa(job #47665)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 3 aprilie 2007 21:39:31
Problema Adapost Scor 4
Compilator c Status done
Runda Arhiva de probleme Marime 3.76 kb
#include <stdio.h>
#include <math.h>
#include <string.h>
#define NMAX 802
#define CMAX (1<<11)
#define INF 666666
#define eps 0.0001

int F[NMAX][NMAX], InQ[CMAX], Q[CMAX], N;
double D[NMAX];
double C[NMAX][NMAX], Xs[NMAX], Ys[NMAX], Xa[NMAX], Ya[NMAX], Cm, Max;
int cup[NMAX], inQ[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;

        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;
        
}