Cod sursa(job #3236483)

Utilizator memecoinMeme Coin memecoin Data 28 iunie 2024 23:23:39
Problema Adapost Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

const int MAXN = 405;
const double INF = 1e9;
const double EPS = 1e-9;

int N;
double x1[MAXN], y1[MAXN], x2[MAXN], y2[MAXN];
vector<int> g[MAXN];
int match[MAXN];
double dist[MAXN][MAXN];

double sqr(double x) {
    return x * x;
}

double distance(int i, int j) {
    return sqrt(sqr(x1[i] - x2[j]) + sqr(y1[i] - y2[j]));
}

bool bfs(double threshold) {
    static int prev[MAXN];
    queue<int> q;
    for (int i = 0; i < N; i++) {
        if (match[i] == -1) {
            q.push(i);
            prev[i] = -1;
        } else {
            prev[i] = -2;
        }
    }
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : g[v]) {
            if (dist[v][u] > threshold) continue;
            if (match[u] == -1) {
                while (v != -1) {
                    int pv = match[v];
                    match[v] = u;
                    match[u] = v;
                    v = pv;
                    u = prev[v];
                }
                return true;
            }
            if (prev[match[u]] == -2) {
                prev[match[u]] = v;
                q.push(match[u]);
            }
        }
    }
    return false;
}

pair<double, double> solve() {
    vector<double> all_distances;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dist[i][j] = distance(i, j);
            all_distances.push_back(dist[i][j]);
        }
    }
    sort(all_distances.begin(), all_distances.end());

    double left = 0, right = all_distances.back();
    while (right - left > EPS) {
        double mid = (left + right) / 2;
        for (int i = 0; i < N; i++) {
            g[i].clear();
            for (int j = 0; j < N; j++) {
                if (dist[i][j] <= mid) {
                    g[i].push_back(j);
                }
            }
        }
        fill(match, match + N, -1);
        int matches = 0;
        while (bfs(mid)) {
            matches++;
        }
        if (matches == N) {
            right = mid;
        } else {
            left = mid;
        }
    }

    double max_dist = right;

    // Calculate minimum sum
    double sum_dist = 0;
    for (int i = 0; i < N; i++) {
        sum_dist += dist[i][match[i]];
    }

    return {max_dist, sum_dist};
}

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

    fin >> N;
    for (int i = 0; i < N; i++)
        fin >> x1[i] >> y1[i];
    for (int i = 0; i < N; i++)
        fin >> x2[i] >> y2[i];

    auto [max_dist, sum_dist] = solve();

    fout << fixed << setprecision(5) << max_dist << " " << sum_dist << endl;

    return 0;
}