Cod sursa(job #3362071)

Utilizator iuli_morariuIuli Morariu iuli_morariu Data 1 august 2026 18:46:23
Problema Adapost Scor 2
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.15 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#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 (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;

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(abs(mch[id].cost) > dist * dist) continue;
        if(cop == sursie || cop == noelle) continue;
        // cerr << "cuplaj[cop] = " << cuplaj[cop] << '\n';
        if(!cuplaj[cop] || pair_up(cuplaj[cop], dist)){
            cuplaj[nod] = cop;
            cuplaj[cop] = nod;
            // 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(!mrc[i] && pair_up(i, dist)){
                ghost_bath_is_asa_peak = 1;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        if(cuplaj[i]) total++;
    }

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

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 = 1; i <= n; i++){
        add_muchie(sursie, i, 1, 0);
        add_muchie(i + n, noelle, 1, 0);
    }

    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 = 1000000.0;
    double sol = 0;
    for(int it = 0; it < 100; 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 << '\n';

    return 0;
}