Cod sursa(job #3202826)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 12 februarie 2024 12:43:57
Problema Adapost Scor 52
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.77 kb
#include <bits/stdc++.h>
#ifdef LOCAL
#define in cin
#define out cout
#endif
#define double long double
using namespace std;

#ifndef LOCAL
ifstream in("adapost.in");
ofstream out("adapost.out");
#endif

const int nmax = 405;
const double inf = 2e9;
int n;
pair<double, double> p1[nmax], p2[nmax];

struct line
{
    int i, j;
    double dist;
    line(int i = 0, int j = 0) : i(i), j(j)
    {
        double x = abs(p1[i].first - p2[j].first);
        double y = abs(p1[i].second - p2[j].second);
        dist = sqrt(x * x + y * y);
    }
    bool operator<(const line &other)
    {
        return dist < other.dist;
    }
    void debug()
    {
        cerr << i << ' ' << j << ' ' << dist << '\n';
    }
} lines[nmax * nmax];

double biadj[nmax][nmax];
int l[nmax], r[nmax];
bool viz[nmax];

bool pairup(int nod, double upp)
{
    if (viz[nod])
        return 0;
    viz[nod] = 1;
    for (int i = 0; i < n; i++)
    {
        if (biadj[nod][i] <= upp)
        {
            if (l[i] == -1)
            {
                l[i] = nod;
                r[nod] = i;
                return 1;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (biadj[nod][i] <= upp)
        {
            if (pairup(l[i], upp))
            {
                l[i] = nod;
                r[nod] = i;
                return 1;
            }
        }
    }
    return 0;
}

bool bipart(double upperbound)
{
    for (int i = 0; i < n; i++)
    {
        l[i] = -1;
        r[i] = -1;
    }
    bool change = 0;
    int pairs = 0;
    do
    {
        change = 0;
        memset(viz, 0, sizeof viz);
        for (int i = 0; i < n; i++)
        {
            if (r[i] == -1)
            {
                if (pairup(i, upperbound))
                {
                    change = 1;
                    pairs++;
                }
            }
        }
    } while (change);
    return pairs == n;
}

int cntE;
int s, d;
vector<int> adj[2 * nmax];
double pi[2 * nmax];
double dist[2 * nmax];
int enter[2 * nmax];

struct edge
{
    int fr, to, c;
    double w;
    edge(int fr = 0, int to = 0, int c = 0, double w = 0) : fr(fr), to(to), c(c), w(w) {}
    int rw()
    {
        return pi[fr] + w - pi[to];
    }
} edges[2 * nmax * nmax];

void addE(int fr, int to, int c, double w)
{
    edges[cntE] = edge(fr, to, c, w);
    adj[fr].push_back(cntE);
    edges[cntE + 1] = edge(to, fr, 0, -w);
    adj[to].push_back(cntE + 1);
    cntE += 2;
}

void resetDist()
{
    for (int i = s; i <= d; i++)
        dist[i] = inf;
}

void topi()
{
    for (int i = s; i <= d; i++)
        pi[i] += dist[i];
}

bool dijkstra()
{
    resetDist();

    struct dijelem
    {
        int a;
        double b;
        dijelem(int a, double b) : a(a), b(b) {}
        bool operator<(const dijelem &other) const
        {
            return b > other.b;
        }
    };

    priority_queue<dijelem> pq;
    dist[s] = 0;
    pq.push({s, dist[s]});

    while (!pq.empty())
    {
        auto nod = pq.top();
        pq.pop();
        for (auto i : adj[nod.a])
        {
            if (edges[i].c == 0)
                continue;
            int to = edges[i].to;
            if (dist[to] > dist[nod.a] + edges[i].rw())
            {
                dist[to] = dist[nod.a] + edges[i].rw();
                pq.push({to, dist[to]});
                enter[to] = i;
            }
        }
    }

    if (dist[d] == inf)
        return 0;
    topi();
    return 1;
}

void dfs(int nod, double &cst)
{
    if (nod == 0)
        return;
    int ind = enter[nod];
    edges[ind].c--;
    edges[ind ^ 1].c++;
    cst += edges[ind].w;
    dfs(edges[ind].fr, cst);
}

int main()
{
    in >> n;
    for (int i = 0; i < n; i++)
    {
        in >> p1[i].first >> p1[i].second;
    }
    for (int i = 0; i < n; i++)
    {
        in >> p2[i].first >> p2[i].second;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            lines[i * (n) + j] = line(i, j);
            biadj[i][j] = lines[i * (n) + j].dist;
        }
    sort(lines, lines + (n * n));
    int st = 0, dr = n * n - 1;
    while (st < dr)
    {
        int mid = (st + dr) / 2;
        if (bipart(lines[mid].dist))
        {
            dr = mid;
        }
        else
        {
            st = mid + 1;
        }
    }
    double upp = lines[st].dist;
    //Acum incepe problema
    s = 0;
    d = 2 * n + 1;
    for (int i = 0; i < n * n; i++)
    {
        if (lines[i].dist > upp)
            break;
        addE(lines[i].i + 1, lines[i].j + 1 + n, 1, lines[i].dist);
    }
    for (int i = 1; i <= n; i++)
    {
        addE(s, i, 1, 0);
    }
    for (int i = n + 1; i <= 2 * n; i++)
    {
        addE(i, d, 1, 0);
    }
    double tcst = 0;
    while (dijkstra())
    {
        double cst = 0;
        dfs(d, cst);
        tcst += cst;
    }
    out << fixed << setprecision(5) << upp << ' ' << tcst;
}