Cod sursa(job #3359516)

Utilizator rares89_Dumitriu Rares rares89_ Data 29 iunie 2026 13:18:55
Problema Adapost Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.17 kb
#include <bits/stdc++.h>

using namespace std;

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

const double INF = 1e18;
const double EPS = 1e-9;

int n;
double xs[405], ys[405], xa[405], ya[405];
double d[405][405];
int pairU[405], pairV[405], distBfs[405];
vector<int> G[405];

double u[405], v[405], minv[405];
int p[405], way[405];
bool used[405];

bool bfs() {
    queue<int> Q;

    for (int i = 1; i <= n; ++i) {
        if (!pairU[i]) {
            distBfs[i] = 0;
            Q.push(i);
        } else {
            distBfs[i] = -1;
        }
    }

    int ok = 0;

    while (!Q.empty()) {
        int node = Q.front();
        Q.pop();

        for (int to : G[node]) {
            if (!pairV[to]) {
                ok = 1;
            } else if (distBfs[pairV[to]] == -1) {
                distBfs[pairV[to]] = distBfs[node] + 1;
                Q.push(pairV[to]);
            }
        }
    }

    return ok;
}

bool dfs(int node) {
    for (int to : G[node]) {
        if (!pairV[to] || distBfs[pairV[to]] == distBfs[node] + 1 && dfs(pairV[to])) {
            pairU[node] = to;
            pairV[to] = node;
            return true;
        }
    }

    distBfs[node] = -1;
    return false;
}

bool check(double lim) {
    for (int i = 1; i <= n; ++i)
        G[i].clear();

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (d[i][j] <= lim + EPS)
                G[i].push_back(j);
        }
    }

    for (int i = 1; i <= n; ++i) {
        pairU[i] = 0;
        pairV[i] = 0;
    }

    int matching = 0;

    while (bfs()) {
        for (int i = 1; i <= n; ++i) {
            if (!pairU[i] && dfs(i))
                ++matching;
        }
    }

    return matching == n;
}

double hungarian(double lim) {
    for (int i = 0; i <= n; ++i) {
        u[i] = v[i] = 0;
        p[i] = way[i] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        p[0] = i;
        int j0 = 0;

        for (int j = 0; j <= n; ++j) {
            minv[j] = INF;
            used[j] = false;
        }

        do {
            used[j0] = true;
            int i0 = p[j0];
            double delta = INF;
            int j1 = 0;

            for (int j = 1; j <= n; ++j) {
                if (!used[j]) {
                    double cost = INF;

                    if (d[i0][j] <= lim + EPS)
                        cost = d[i0][j];

                    double cur = cost - u[i0] - v[j];

                    if (cur < minv[j]) {
                        minv[j] = cur;
                        way[j] = j0;
                    }

                    if (minv[j] < delta) {
                        delta = minv[j];
                        j1 = j;
                    }
                }
            }

            for (int j = 0; j <= n; ++j) {
                if (used[j]) {
                    u[p[j]] += delta;
                    v[j] -= delta;
                } else {
                    minv[j] -= delta;
                }
            }

            j0 = j1;
        } while (p[j0]);

        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0);
    }

    return -v[0];
}

int main() {
    fin >> n;

    for (int i = 1; i <= n; ++i)
        fin >> xs[i] >> ys[i];

    for (int i = 1; i <= n; ++i)
        fin >> xa[i] >> ya[i];

    vector<double> values;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            double dx = xs[i] - xa[j];
            double dy = ys[i] - ya[j];

            d[i][j] = sqrt(dx * dx + dy * dy);
            values.push_back(d[i][j]);
        }
    }

    sort(values.begin(), values.end());

    int st = 0, dr = (int)values.size() - 1;
    double best = values.back();

    while (st <= dr) {
        int mid = (st + dr) / 2;

        if (check(values[mid])) {
            best = values[mid];
            dr = mid - 1;
        } else {
            st = mid + 1;
        }
    }

    double sum = hungarian(best);

    fout << fixed << setprecision(5) << best << " " << sum << "\n";

    return 0;
}