Cod sursa(job #3362078)

Utilizator iuli_morariuIuli Morariu iuli_morariu Data 2 august 2026 02:45:43
Problema Adapost Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 7.09 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <cmath>
#include <vector>
#include <stack>
#include <iomanip>
#include <queue>
// #include <bits/std++.h>
#define in  fin
#define out fout

using namespace std;
const int NMAX = 400 * 2 + 5;
const double eps = 1e-5;

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

struct muchie{
    int x, y, pereche, c, f;
    double cost;
};

struct punct{
    double x, y;
};

double distanta(punct &a, punct &b){
    return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );
}

vector<muchie> mch;
vector<int> g[NMAX];
int sursie, noelle;
int cuplaj[NMAX];
bool mrc[NMAX];
int n;
double unchii[NMAX], perchance[NMAX], the_real_ones[NMAX];
pair<int, int> last[NMAX];

void add_muchie(int x, int y, int c, double cost){
    int id = mch.size(), idp = id + 1;
    mch.push_back({x, y, idp, c, 0,  cost});
    mch.push_back({y, x, id,  0, 0, -cost});

    g[x].push_back(id);
    g[y].push_back(idp);
}

bool pair_up(int nod, double dist){
    if(mrc[nod]) return 0;
    mrc[nod] = 1;
    
    // cerr << "dist = " << dist << '\n';

    for(const int &id : g[nod]){
        int cop = mch[id].y;
        if(mch[id].cost > dist) continue;
        if(-mch[id].cost > dist) continue;
        if(cop == sursie || cop == noelle) continue; // ei nu conteaza la cuplaj
        // cerr << "cuplaj[cop] = " << cuplaj[cop] << '\n';
        if(!cuplaj[cop] || pair_up(cuplaj[cop], dist)){
            cuplaj[cop] = nod;
            cuplaj[nod] = cop;
            // cerr << "--> fac pair up" << '\n';
            return 1;
        }
    }
    return 0;
}

bool verifica_te_rog(double dist){
    for(int i = 1; i <= 2 * n + 2; i++){
        cuplaj[i] = 0;
    }
    int total = 0;
    // cerr << "incep sa verific dist = " << fixed << setprecision(3) << dist << '\n';
    bool ghost_bath_is_asa_peak = 1; // in special albumui burial
    while(ghost_bath_is_asa_peak){ // asta e ca un while true cu conditia asta...
        ghost_bath_is_asa_peak = 0;
        for(int i = 1; i <= n; i++) mrc[i] = 0;
        for(int i = 1; i <= n; i++){
            // cerr << "i = " << i << '\n';
            if(!cuplaj[i] && pair_up(i, dist)){
                ghost_bath_is_asa_peak = 1;
                total++;
                // cerr << "adaug unu pentru i = " << i << '\n';
            }
        }
    }

    // cerr << "total = " << total << '\n';

    return (total == n); // toti gasesc adapost in dist rezonabila
}

// ew flux
void clopot_barbat_vad(){
    for(int i = 1; i <= 2 * n + 2; i++){
        unchii[i] = INT_MAX;
        mrc[i] = 0;
    }

    queue<int> q;
    q.push(sursie);
    unchii[sursie] = 0;
    mrc[sursie] = 1;

    while(!q.empty()){
        int x = q.front(); q.pop();
        for(const int &id : g[x]){
            int y = mch[id].y;
            if(unchii[y] > unchii[x] + mch[id].cost && mch[id].c > mch[id].f){
                unchii[y] = unchii[x] + mch[id].cost;
                if(!mrc[y]){
                    q.push(y);
                    mrc[y] = 1;
                }
            }
        }
        mrc[x] = 0;
    }
}

double cost = 0, flux = 0;
double maxim_ude = 0;
bool deschistra(){
    for(int i = 1; i <= 2 * n + 2; i++){
        perchance[i] = INT_MAX;
        last[i] = {0, -1};
    }

    priority_queue< pair<double, int>, vector< pair<double, int> >, greater< pair<double, int> > > pq;
    perchance[sursie] = 0;
    the_real_ones[sursie] = 0;
    pq.push({0, sursie});
    
    while(!pq.empty()){
        int x = pq.top().second;
        double d = pq.top().first;
        pq.pop();

        // cerr << "x initial = " << x << " d = " << d << '\n';

        if(d != perchance[x]) continue;

        // benighted

        // cerr << "x = " << x << '\n';

        for(const int &id : g[x]){
            int y = mch[id].y;
            if(mch[id].c == mch[id].f) continue;

            if(mch[id].cost > maxim_ude) continue;
            if(-mch[id].cost > maxim_ude) continue;

            // cerr << "--> y = " << y << '\n';

            double im_a_new_soul = perchance[x] + mch[id].cost + unchii[x] - unchii[y];
            // cerr << "--> new = " << im_a_new_soul << " per = " << perchance[y] << '\n';
            if(im_a_new_soul < perchance[y]){
                // cerr << "----> sa stii ca am chiar intrat\n";
                perchance[y] = im_a_new_soul;
                the_real_ones[y] = the_real_ones[x] + mch[id].cost;
                pq.push({perchance[y], y});
                last[y] = {x, id};
                // im a new soul, i came to this strange world
                // hoping i could learn a bit 'bout how to give and take
                // but since i came here
                // felt the joy and the fear
                // finding myself making every posible mistake
            }
        }
    }

    // cerr << "am iesit cu bile\n";

    for(int i = 1; i <= 2 * n + 2; i++){
        unchii[i] = the_real_ones[i];
    }

    // cerr << "perchance = " << perchance[noelle] << '\n';

    if(perchance[noelle] == INT_MAX){
        return 0;
    }

    // gasesc pathul
    int minim_ude = INT_MAX;
    int nod = noelle;
    double sum = 0;
    while(nod != sursie){
        // cerr << "nod = " << nod << '\n';
        int id = last[nod].second;
        // sum += mch[id].cost;
        minim_ude = min(minim_ude, mch[id].c - mch[id].f);
        nod = last[nod].first;
    }

    // cerr << "minim_ude = " << minim_ude << '\n';
    // cerr << "perchance[noelle] = " << perchance[noelle] << " last = " << last[noelle].first << '\n';
    // cerr << "sum = " << sum << " real = " << the_real_ones[noelle] << '\n';

    flux += minim_ude;
    cost += (double)minim_ude * the_real_ones[noelle];

    nod = noelle;
    while(nod != sursie){
        int id = last[nod].second;
        mch[id].f += minim_ude;
        mch[ mch[id].pereche ].f -= minim_ude;
        nod = last[nod].first;
    }

    return 1;
}

void fa_flux_te_ROG(){
    clopot_barbat_vad();
    // cerr << "Dupa clopotul\n";
    while(deschistra());
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    in >> n;
    punct sold[n], adp[n];

    for(int i = 0; i < n; i++) in >> sold[i].x >> sold[i].y;
    for(int i = 0; i < n; i++) in >>  adp[i].x >>  adp[i].y;

    sursie = 2 * n + 1;
    noelle = sursie + 1;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            // cout << "i = " << i << " j = " << j << " dist = " << distanta(sold[i], adp[j]) << '\n';
            add_muchie(i + 1, j + n + 1, 1, distanta(sold[i], adp[j]));
        }
    }

    double l = 0, r = 10000.0;
    double sol = 0;
    for(int it = 0; it < 60; it++){
        double m = (l + r) / 2.0;
        if(verifica_te_rog(m)){
            sol = m;
            r = m - eps;
        }else l = m + eps;
    }

    out << fixed << setprecision(4) << sol << " ";

    maxim_ude = sol;

    // cerr << "sursie = " << sursie << " noelle = " << noelle << '\n';

    for(int i = 1; i <= n; i++){
        add_muchie(sursie, i, 1, 0);
        add_muchie(i + n, noelle, 1, 0);
    }

    // cerr << "am ajuns aici\n";

    // ew flux
    fa_flux_te_ROG();
    out << cost << '\n';
    // out << "flux = " << flux << '\n';

    return 0;
}