Cod sursa(job #3236489)

Utilizator memecoinMeme Coin memecoin Data 28 iunie 2024 23:33:04
Problema Adapost Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.7 kb
#include <iostream>
#include <fstream>
#include <vector>
#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];
double dist[MAXN][MAXN];
vector<double> all_distances;

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]));
}

pair<vector<int>, double> hungarian(const vector<vector<double>>& cost) {
    int n = cost.size();
    vector<double> u(n), v(n);
    vector<int> p(n), way(n);
    vector<double> minv(n);
    vector<bool> used(n);
    
    for (int i = 0; i < n; ++i) {
        p[0] = i;
        int j0 = 0;
        fill(minv.begin(), minv.end(), INF);
        fill(used.begin(), used.end(), false);
        do {
            used[j0] = true;
            int i0 = p[j0], j1;
            double delta = INF;
            for (int j = 1; j < n; ++j)
                if (!used[j]) {
                    double cur = cost[i0][j] - 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] != i);
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0);
    }

    vector<int> matching(n);
    for (int i = 0; i < n; ++i)
        matching[p[i]] = i;
    
    double total_cost = 0;
    for (int i = 0; i < n; ++i)
        total_cost += cost[i][matching[i]];
    
    return {matching, total_cost};
}

pair<double, double> solve() {
    all_distances.clear();
    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());
    all_distances.erase(unique(all_distances.begin(), all_distances.end()), all_distances.end());

    int left = 0, right = all_distances.size() - 1;
    vector<int> best_matching;
    while (left <= right) {
        int mid = (left + right) / 2;
        double threshold = all_distances[mid];
        
        vector<vector<double>> cost(N, vector<double>(N));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cost[i][j] = (dist[i][j] <= threshold) ? dist[i][j] : INF;
            }
        }
        
        auto [matching, _] = hungarian(cost);
        bool possible = true;
        for (int i = 0; i < N; i++) {
            if (dist[i][matching[i]] > threshold) {
                possible = false;
                break;
            }
        }
        
        if (possible) {
            right = mid - 1;
            best_matching = matching;
        } else {
            left = mid + 1;
        }
    }

    double max_dist = all_distances[left];
    double sum_dist = 0;
    for (int i = 0; i < N; i++) {
        sum_dist += dist[i][best_matching[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;
}