Cod sursa(job #64919)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 6 iunie 2007 11:50:19
Problema Adapost Scor 9
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.14 kb
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>


#define NMAX 404
#define MMAX 2*401
#define QMAX ((1<<16)-1)
#define INF 666000666
#define eps 1e-4
#define f first
#define s second

using namespace std;

int N, Cup[NMAX], F[NMAX];
char Fl[NMAX][NMAX];
vector<pair<double,int> > D[NMAX];
double X[NMAX], Y[NMAX], Rmin, Dmin, Dd[NMAX][MMAX], Dist[MMAX];
int t[MMAX], inQ[MMAX], Q[QMAX+10], cup[MMAX], type[MMAX];

void read()
{
        int i, j;
        double x, y;

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

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

        for (i = 1; i <= N; i++)
            { scanf("%lf %lf", &X[i], &Y[i]); D[i].push_back(make_pair(-INF,0)); }

        for (i = 1; i <= N; i++)
        {
                scanf("%lf %lf", &x, &y);
                for (j = 1; j <= N; j++)
                {
                    D[j].push_back(make_pair(sqrt( (X[j]-x)*(X[j]-x) + (Y[j]-y)*(Y[j]-y) ), i));
                    Dd[j][i] = D[j][i].f;
                }
        }

        for (i = 1; i <= N; i++) sort(D[i].begin(), D[i].end());
}

int pairthembaby(int i, double dmax)
{
        int j, x;
        
        if (F[i]) return 0;
        F[i] = 1;
        for (j = 1; j <= N && D[i][j].f <= dmax; j++)
            if ((!Cup[ D[i][j].s ]) || (pairthembaby(Cup[D[i][j].s], dmax)))
            {
                Cup[ D[i][j].s ] = i;
                return 1;
            }
        return 0;
}

void joint(double dmax)
{
        int i;

        for (i = 1; i <= N; i++)
            if (!pairthembaby(i,dmax))
            {
                memset(F,0,sizeof(F));
                pairthembaby(i,dmax);
            }
}

void bf(int tap)
{
        int i, j, lo, hi;
        double min;

        for (i = 0; i < MMAX; i++)
            t[i] = inQ[i] = type[i] = 0, Dist[i] = INF;

        Q[0] = tap; inQ[tap] = 0; Dist[tap] = 0;

        for (lo = 0, hi = 1; lo != hi; lo = (lo+1)&QMAX)
        {
                i = Q[lo];
                if (i <= N)
                {
                        for (j = N<<1; j > N; j--)
                            if ( (Fl[i][j]=='0') && (Dd[i][j]<=Rmin) && (Dist[j]>Dist[i]+Dd[i][j]) )
                            {
                                Dist[j] = Dist[i]+Dd[i][j];
                                t[j] = i;
                                if (!inQ[j]) inQ[j] = 1, Q[hi] = j, hi = (hi+1)&QMAX;
                            }
                }
                else
                {
                        j = cup[i];
                        if ( (Fl[j][i] == '1') && (Dist[j]>Dist[i]-Dd[j][i]) )
                        {
                                Dist[j] = Dist[i]-Dd[j][i];
                                t[j] = i; type[j] = 1;
                                if (!inQ[j]) inQ[j] = 1, Q[hi] = j, hi = (hi+1)&QMAX;
                        }
                }
        }

        min = INF; j = tap;
        for (i = N<<1; i > N; i--)
            if (!cup[i] && min > Dist[i]) min = Dist[i], j = i;

        Dmin += min;
        for (i=j; t[i]; i=t[i])
            if (!type[i])
            {
                Fl[t[i]][i] = '1';
                cup[i] = t[i];
            }
            else Fl[i][t[i]] = '0';
}

void solve()
{
        int flow, i, j;
        double lo = 0, hi = (1<<28), mij;

        while (lo<=hi)
        {
                mij = (lo+hi)/2.0;
                memset(Cup,0,sizeof(Cup));
                joint(mij);
                for (i = 1, flow = 0; i <= N; i++) flow += (Cup[i]>0);
                if (flow == N) Rmin = mij, hi = mij-eps;
                else lo = mij+eps;
        }

        memset(Fl,'0',sizeof(Fl));

        for (i = 1; i <= N; i++)
            for (j = 1; j <= N; j++) Dd[i][N+j] = Dd[i][j], Dd[i][j] = INF;
            
        for (i = 1; i <= N; i++) bf(i);
}

void write()
{
        freopen("adapost.out", "w", stdout);
        printf("%lf %lf\n", Rmin, Dmin);
}

int main()
{
        read();
        solve();
        write();
        return 0;
}