Cod sursa(job #603434)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 16 iulie 2011 10:47:57
Problema Adapost Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>

using namespace std;

#define maxn 810
#define inf 1000000000
#define maxq 640000

int n, i, j, k, tot;
pair<double, double> s[maxn], a[maxn];
double sol, ctot, sf, cost[maxn][maxn], dist[maxn];
int c[maxn][maxn], f[maxn][maxn], t[maxn], fol[maxn], q[maxn*maxn];
vector<int> v[maxn];

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

void build_graph(double mx)
{
    memset(f, 0, sizeof(f));
    memset(c, 0, sizeof(c));
    for(int i=0; i<=2*n+1; ++i)
        v[i].clear();

   // printf("%.3lf\n", mx);

    for(int i=1; i<=n; ++i)
    {
        c[0][i]=c[i+n][n*2+1]=1;
      //  v[0].push_back(i);
      //  v[i].push_back(0);
      //  v[i+n].push_back(n*2+1);
      //  v[n*2+1].push_back(i+n);

        for(int j=1; j<=n; ++j)
            if(!(cost[i][j+n]>mx))
            {
             //   printf("*");
              //  v[i].push_back(j+n);
              //  v[j+n].push_back(i);
                c[i][j+n]=1;
            }
    }
}

int flux()
{
    memset(fol, 0, sizeof(fol));

    int nod, fiu, qr=1;
    q[qr]=0;

    dist[i]=0;
    fol[0]=1;
    for(int i=1; i<=2*n+1; ++i)
        dist[i]=inf;

    for(int i=1; i<=qr; ++i)
    {
        nod=q[i%maxq];
        fol[nod]=0;
        for(int j=0; j<2*n+2; ++j)
        {
            fiu=j;
            if(c[nod][fiu]>f[nod][fiu] && dist[nod]+cost[nod][fiu]<dist[fiu])
            {
                t[fiu]=nod;
                dist[fiu]=dist[nod]+cost[nod][fiu];
                if(!fol[fiu])
                {
                    fol[fiu]=1;
                    q[(++qr)%maxq]=fiu;
                }
            }
        }
    }

    if(dist[2*n+1]==inf)
        return 0;

    int flx=inf;

    nod=2*n+1;
    while(nod)
    {
        flx=min(flx, c[t[nod]][nod]-f[t[nod]][nod]);
        nod=t[nod];
    }

    tot+=flx;
    ctot+=flx*dist[2*n+1];

    nod=2*n+1;
    while(nod)
    {
        f[t[nod]][nod]+=flx;
        f[nod][t[nod]]-=flx;
        nod=t[nod];
    }

    return 1;
}

int main()
{
    freopen("adapost.in", "r", stdin);
    freopen("adapost.out", "w", stdout);

    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
        scanf("%lf%lf", &s[i].first, &s[i].second);
    for(int i=1; i<=n; ++i)
        scanf("%lf%lf", &a[i].first, &a[i].second);

    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
        {
            cost[i][j+n]=distanta(s[i].first, s[i].second, a[j].first, a[j].second);
            cost[j+n][i]=-cost[i][j+n];
        }

    double med, left=0, right=1500;

    for(int pas=1; pas<=30; ++pas)
    {
        med=(left+right)/2;

        build_graph(med);

        tot=0;
        ctot=0;

        while(flux());

        if(tot==n)
        {
            sol=med;
            sf=ctot;
            right=med;
        }
        else
            left=med;
    }

    printf("%.5lf %.5lf\n", sol, sf);

    return 0;
}