Cod sursa(job #2061262)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 9 noiembrie 2017 00:39:42
Problema Adapost Scor 38
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.09 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("adapost.in");
ofstream fout ("adapost.out");

typedef long long ll;
const int Nmax = 808;
const double eps = 1e-7;

int i, n;
ll st, dr, mid;
double X, Y;

struct point
{
    int x, y;
} a[Nmax], b[Nmax];

ll dist(point a, point b)
{
    return (ll) (a.x - b.x) * (a.x - b.x) + (ll) (a.y - b.y) * (a.y - b.y);
}


class GreatGraph
{
    vector<int> v[Nmax];
    bool used[Nmax];
    double cost[Nmax][Nmax], d[Nmax];
    int cap[Nmax][Nmax], t[Nmax], L[Nmax], R[Nmax];

    void add_edge(int x, int y, double cc)
    {
        v[x].push_back(y);
        v[y].push_back(x);

        cost[x][y] = cc;
        cost[y][x] = -cc;

        cap[x][y] = 1;
        cap[y][x] = 0;
    }

    bool bellman()
    {
        queue<int> q;

        memset(t, -1, sizeof(t));
        memset(used, 0, sizeof(used));
        for(int i=1; i<=2*n+1; ++i) d[i] = 1e9;

        d[0] = 0;
        t[0] = 1;
        q.push(0);
        used[0] = 1;

        while(!q.empty())
        {
            int node = q.front();
            q.pop();
            used[node] = 0;

            for(auto it : v[node])
                if(cap[node][it] && d[it] > eps + d[node] + cost[node][it])
                {
                    d[it] = d[node] + cost[node][it];
                    t[it] = node;

                    if(!used[it])
                    {
                        used[it] = 1;
                        q.push(it);
                    }
                }
        }

        if(d[2*n+1] != 1e9) return 1;
        return 0;
    }

    bool cupleaza(int node)
    {
        used[node] = 1;
        for(auto it : v[node])
            if(!R[it])
            {
                L[node] = it;
                R[it] = node;
                return 1;
            }

        for(auto it : v[node])
            if(!used[R[it]] && cupleaza(R[it]))
            {
                L[node] = it;
                R[it] = node;
                return 1;
            }
        return 0;
    }

    public:
        bool check(ll lim)
        {
            int i, j;
            memset(L, 0, sizeof(L));
            memset(R, 0, sizeof(R));

            for(i=1; i<=n; ++i)
                for(j=1; j<=n; ++j)
                    if(dist(a[i], b[j]) <= lim)
                        v[i].push_back(j);

            bool done = 1;
            while(done)
            {
                done = 0;
                memset(used, 0, sizeof(used));
                for(i=1; i<=n; ++i)
                    if(!L[i] && !used[i])
                        done |= cupleaza(i);
            }

            int cnt = 0;
            for(i=1; i<=n; ++i)
            {
                v[i].clear();
                if(L[i]) ++cnt;
            }

            return (cnt == n);
        }

        double max_flow_min_cost(int lim)
        {
            int i, j;
            for(i=1; i<=n; ++i)
                for(j=1; j<=n; ++j)
                    if(dist(a[i], b[j]) <= lim)
                        add_edge(i, n+j, sqrt(dist(a[i], b[j])));

            for(i=1; i<=n; ++i) add_edge(0, i, 0);
            for(i=n+1; i<=2*n; ++i) add_edge(i, 2*n+1, 0);

            int node, dad;
            double Cost = 0;
            while(bellman())
            {
                node = 2 * n + 1;
                while(node)
                {
                    dad = t[node];
                    cap[dad][node] --;
                    cap[node][dad] ++;
                    Cost += cost[dad][node];
                    node = dad;
                }
            }

            return Cost;
        }
} graph;

int main()
{
    fin >> n;
    for(i=1; i<=n; ++i)
    {
        fin >> X >> Y;
        a[i].x = (int)(X * 1000);
        a[i].y = (int)(Y * 1000);
    }

    for(i=1; i<=n; ++i)
    {
        fin >> X >> Y;
        b[i].x = (int)(X * 1000);
        b[i].y = (int)(Y * 1000);
    }

    st = 0; dr = 2e12;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(graph.check(mid)) dr = mid - 1;
            else st = mid + 1;
    }

    fout << setprecision(5) << fixed;
    fout << sqrt(st) / 1000 << ' ';
    fout << graph.max_flow_min_cost(st) / 1000 << '\n';

    return 0;
}