Cod sursa(job #3236482)

Utilizator memecoinMeme Coin memecoin Data 28 iunie 2024 23:22:19
Problema Adapost Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.16 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-6;

int N;
double x1[MAXN], y1_[MAXN], x2[MAXN], y2_[MAXN];
double dist[MAXN][MAXN];
double lx[MAXN], ly[MAXN], slack[MAXN];
int xy[MAXN], yx[MAXN], previous[MAXN];
bool S[MAXN], T[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]));
}

void add_to_tree(int x, int prevx) {
    S[x] = true;
    previous[x] = prevx;
    for (int y = 0; y < N; y++)
        if (lx[x] + ly[y] - dist[x][y] < slack[y] - EPS) {
            slack[y] = lx[x] + ly[y] - dist[x][y];
            yx[y] = x;
        }
}

void update_labels() {
    double delta = INF;
    for (int y = 0; y < N; y++)
        if (!T[y])
            delta = min(delta, slack[y]);
    for (int x = 0; x < N; x++)
        if (S[x]) lx[x] -= delta;
    for (int y = 0; y < N; y++)
        if (T[y]) ly[y] += delta;
        else slack[y] -= delta;
}

void augment() {
    if (xy[N - 1] != -1) return;
    int x, y, root;
    int q[MAXN], wr = 0, rd = 0;
    for (int i = 0; i < N; i++) {
        S[i] = T[i] = false;
        previous[i] = -1;
    }
    for (x = 0; x < N; x++)
        if (xy[x] == -1) {
            q[wr++] = root = x;
            previous[x] = -2;
            S[x] = true;
            break;
        }
    for (y = 0; y < N; y++) {
        slack[y] = lx[root] + ly[y] - dist[root][y];
        yx[y] = root;
    }
    while (true) {
        while (rd < wr) {
            x = q[rd++];
            for (y = 0; y < N; y++)
                if (!T[y] && abs(lx[x] + ly[y] - dist[x][y]) < EPS) {
                    if (yx[y] == -1) {
                        while (y != -2) {
                            int ty = xy[x];
                            yx[y] = x;
                            xy[x] = y;
                            x = previous[x];
                            y = ty;
                        }
                        return;
                    }
                    T[y] = true;
                    q[wr++] = yx[y];
                    add_to_tree(yx[y], x);
                }
        }
        update_labels();
        wr = rd = 0;
        for (y = 0; y < N; y++)
            if (!T[y] && abs(slack[y]) < EPS) {
                if (yx[y] == -1) {
                    x = yx[y];
                    while (y != -2) {
                        int ty = xy[x];
                        yx[y] = x;
                        xy[x] = y;
                        x = previous[x];
                        y = ty;
                    }
                    return;
                } else {
                    T[y] = true;
                    if (!S[yx[y]]) {
                        q[wr++] = yx[y];
                        add_to_tree(yx[y], yx[y]);
                    }
                }
            }
    }
}

double hungarian() {
    for (int i = 0; i < N; i++) {
        lx[i] = ly[i] = 0;
        xy[i] = yx[i] = -1;
        for (int j = 0; j < N; j++)
            lx[i] = max(lx[i], dist[i][j]);
    }
    for (int i = 0; i < N; i++)
        augment();
    double ret = 0;
    for (int i = 0; i < N; i++)
        ret += dist[i][xy[i]];
    return ret;
}

bool check(double mid) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            dist[i][j] = (distance(i, j) <= mid ? distance(i, j) : INF);
    hungarian();
    for (int i = 0; i < N; i++)
        if (xy[i] == -1) return false;
    return true;
}

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

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

    double max_dist = hi;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            dist[i][j] = distance(i, j);
    double sum_dist = hungarian();

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

    return 0;
}