Cod sursa(job #20849)

Utilizator diaDiana Adrisor dia Data 22 februarie 2007 14:36:13
Problema Adapost Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <stdio.h>
#define NMAX 444
#define eps 0.000001
#define INF 666000666

long double D[NMAX][NMAX], P[2][NMAX], R1, R2, Dist[NMAX];
int N, Flow, F[NMAX][NMAX], Q[2*NMAX*NMAX], InQ[NMAX], t[NMAX];

long double dist(long double x1, long double y1, long double x2, long double y2)
{
        return ( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );
}

int flow(int x, double max)
{
        int i, nod, lo, hi;

        for (i = 0; i < NMAX; i++) Q[i] = 0, InQ[i] = 0, t[i] = -1;
        for (i = 0; i < NMAX; i++) Dist[i] = INF;

        Q[0] = x;
        InQ[x] = 1;
        Dist[x] = 0;

        for (lo = 0, hi = 1; lo <= hi; lo++)
        {
                nod = Q[lo];
                for (i = 1; i <= 2*N; i++)
                    if ((D[nod][i]-max <= eps) && (F[nod][i]) && (t[i]==-1) && (Dist[i] > Dist[nod]+D[nod][i]))
                    {
                        Q[hi++] = i;
                        InQ[i] = 1;
                        if (t[i] == -1) t[i] = nod;
                        Dist[i] = Dist[nod]+D[nod][i];
                        if (i == 2*N) return 1;
                    }
        }
        return 0;
}

int main()
{
        int i, j;
        long double x, y, max = -INF, lo, hi, mid, cmax;

        freopen("adapost.in", "r", stdin);
        scanf("%d\n", &N);

        for (i = 1; i <= N; i++)
            scanf("%llf %llf", &P[0][i], &P[1][i]);

        for (i = 0; i < NMAX; i++)
            for (j = 0; j < NMAX; j++) D[i][j] = INF;

        for (i = 1; i <= N; i++)
            for (j = 1; j <= N; j++)
            {
                scanf("%llf %llf", &x, &y);
                D[j][N+i] = dist(x, y, P[0][j], P[1][j]);
                if (D[j][N+i]-max > eps) max = D[j][N+i];
            }

        for (lo = 0, hi = max, mid = (lo+hi)/2.0; lo <= hi; mid = (lo+hi)/2.0)
        {
                Flow = 0;
                cmax = 0;
                for (j = 1; j <= N; j++)
                      if (flow(j, mid*mid))
                      {
                          Flow++;
                          cmax += Dist[2*N];
                          for (i = t[2*N]; i > 0; i = t[i])
                              F[i][ t[i] ]++, F[ t[i] ][i]--;
                      }
                if (Flow == N)
                {
                   R1 = mid; R2 = cmax;
                   hi = mid-1;
                }
                else lo = mid+1;
        }

        freopen("adapost.out", "w", stdout);
        printf("%llf %llf\n", R1, R2);

        return 0;
        
}