Cod sursa(job #1699)

Utilizator filipbFilip Cristian Buruiana filipb Data 14 decembrie 2006 16:01:46
Problema Adapost Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 4.39 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define INF 1.e11
#define EPS 0.001
#define NMax 412

int N, U[NMax*2], G[NMax*2][NMax*2], deg[NMax*2], st[NMax], dr[2*NMax], 
    h = 0, bst, F[NMax * 2][NMax * 2], C[NMax * 2][NMax * 2], S, D,
    q[NMax * NMax * 4];
double XS[NMax], YS[NMax], XA[NMax], YA[NMax], DST[NMax * NMax], d[2*NMax],
       cst[NMax * 2][NMax * 2], TMIN = 0;

double modul(double A)
{ if (A < 0) return -A; return A; }

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

int cmp(const void *a, const void *b)
{
    double *A = (double *)a, *B = (double *)b;
    
    if (fabs(*A - *B) < EPS) return 0;
    if (*A > *B) return +1;
    return -1;
}

int cupleaza(int nod)
{
     int i, nd;
     
     if (U[nod]) return 0;
     U[nod] = 1;
     
     for (i = 1; i <= deg[nod]; i++)
     {
         nd = G[nod][i];
         if (!dr[nd] || cupleaza(dr[nd]))
         { st[nod] = nd; dr[nd] = nod; return 1; }
     }
     return 0;
}

int cuplaj(double X)
{
     int i, j, nr = 0;
     
     memset(U, 0, sizeof(U));
     memset(st, 0, sizeof(st));
     memset(dr, 0, sizeof(dr));
     memset(deg, 0, sizeof(deg));
     
     for (i = 1; i <= N; i++)
         for (j = 1; j <= N; j++)
             if (X > dist(XS[i], YS[i], XA[j], YA[j]) - EPS)
                G[i][++deg[i]] = N+j,
                G[N+j][++deg[N+j]] = i;
                
     for (i = 1; i <= N; i++)
     {
         if (st[i]) continue;
         if (cupleaza(i)) nr++;
         else
         {
             memset(U, 0, sizeof(U));
             if (cupleaza(i)) nr++;
         }
     }
    
     return (nr == N);             
}

void bellman(void)
{
    int i, ql, qr, nd;
    
    for (i = S; i <= D; i++) d[i] = INF;
    d[S] = 0;
    
    for (q[qr=ql=0]=S; qr <= ql; qr++)
    {
        nd = q[qr];
        for (i = 1; i <= deg[nd]; i++)
            if (F[nd][G[nd][i]] < C[nd][G[nd][i]] &&
                   d[G[nd][i]] > d[nd] + cst[nd][G[nd][i]])
                 q[++ql] = G[nd][i],  
                 d[G[nd][i]] = d[nd] + cst[nd][G[nd][i]],
                 U[G[nd][i]] = nd;                            
    }
       
}

int main(void)
{
    int i, j, l, r, m, ok;
    double A, B;
    
    freopen("adapost.in", "r", stdin);
    freopen("adapost.out", "w", stdout);
    
    scanf("%d", &N);
    for (i = 1; i <= N; i++)
    {
        scanf("%lf %lf", &A, &B);
        XS[i] = A; YS[i] = B;
    }
    for (i = 1; i <= N; i++)
    {
        scanf("%lf %lf", &A, &B);
        XA[i] = A; YA[i] = B;
    }
    
    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
            cst[i][j+N] = cst[j+N][i] = dist(XS[i], YS[i], XA[j], YA[j]);
            
    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
            DST[h++] = cst[i][j+N];

    qsort(DST, h, sizeof(double), cmp);
       
    for (i = 1, j = 0; i < h; i++)
        if (fabs(DST[i] - DST[j]) >= EPS)
           DST[++j] = DST[i];
    
    l = 0; r = h; bst = h-1;
    while (l <= r)
    {
          m = (l + r) >> 1;
          ok = cuplaj(DST[m]);
          if (ok) r = m-1, bst = m;
          else l = m+1;
    }
                
    memset(deg, 0, sizeof(deg));
    S = 0; D = 2*N+1;
    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
            if (DST[bst] > cst[i][j+N] - EPS)
               G[i][++deg[i]] = N+j,
               G[N+j][++deg[N+j]] = i,
               C[i][N+j] = 1;
    for (i = 1; i <= N; i++) 
        G[S][++deg[S]] = i,
        G[i][++deg[i]] = S,
        C[S][i] = 1;
        
    for (j = N+1; j <= 2*N; j++) 
        G[j][++deg[j]] = D,
        G[D][++deg[D]] = j,
        C[j][D] = 1;
    
    for (j = 1; j <= N; j++)
    {
        bellman();
        for (i = D; i != S; i = U[i])
        {
            F[U[i]][i]++, F[i][U[i]]--;
            if (F[U[i]][i] == 0)
               cst[i][U[i]] = cst[U[i]][i] = modul(cst[i][U[i]]);
            else
               cst[U[i]][i] = modul(cst[U[i]][i]), cst[i][U[i]] = -cst[U[i]][i]; 
        }
                
    }
    
    for (i = 1; i <= N; i++)
        for (j = N+1; j <= 2*N; j++)
            if (F[i][j] > 0)
               TMIN += cst[i][j];
        
    printf("%.5f %.5f\n", DST[bst], TMIN);

//    for (; ;);
        
    return 0;
}