Cod sursa(job #3236485)

Utilizator memecoinMeme Coin memecoin Data 28 iunie 2024 23:26:38
Problema Adapost Scor 43
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>

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];
bool used[MAXN];
int match[MAXN];
vector<int> g[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 try_kuhn(int v) {
    if (used[v]) return false;
    used[v] = true;
    for (int to : g[v]) {
        if (match[to] == -1 || try_kuhn(match[to])) {
            match[to] = v;
            return true;
        }
    }
    return false;
}

bool check(double mid) {
    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);
            }
        }
    }

    memset(match, -1, sizeof(match));
    for (int v = 0; v < N; v++) {
        memset(used, 0, sizeof(used));
        if (!try_kuhn(v)) return false;
    }
    return true;
}

pair<double, double> solve() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dist[i][j] = distance(i, j);
        }
    }

    double left = 0, right = 1500;
    while (right - left > EPS) {
        double mid = (left + right) / 2;
        if (check(mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }

    double max_dist = right;

    // Calculate minimum sum
    check(max_dist + EPS);
    double sum_dist = 0;
    for (int i = 0; i < N; i++) {
        sum_dist += dist[match[i]][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;
}