Cod sursa(job #2937764)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 10 noiembrie 2022 22:12:41
Problema Adapost Scor 6
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.39 kb
/// proba cerinta 1
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;

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

const int max_size = 8e2 + 9;
const double INF = 1e9 + 1;

struct str{
    int nod;
    double val;
    bool operator < (const str &aux) const
    {
        return val > aux.val;
    }
};

#define pdd pair <double, double>

double cap[max_size][max_size], cost[max_size][max_size], d[max_size][max_size], aux[max_size];
int t[max_size], dr[max_size], st[max_size], n;
pdd sld[max_size], adp[max_size];
bitset <max_size> viz;
vector <int> mc[max_size];
priority_queue <str> pq;

void bf ()
{

}

bool djk ()
{

}

bool pairup (int nod)
{
    if (viz[nod])
    {
        return false;
    }
    viz[nod] = 1;
    for (auto f : mc[nod])
    {
        if (dr[f] == 0)
        {
            st[nod] = f;
            dr[f] = nod;
            return true;
        }
    }
    for (auto f : mc[nod])
    {
        if (pairup(dr[f]))
        {
            st[nod] = f;
            dr[f] = nod;
            return true;
        }
    }
    return false;
}

bool verif (double x)
{
    for (int i = 1; i <= 2 * n + 2; i++)
    {
        mc[i].clear();
    }
    for (int i = 1; i <= n; i++)
    {
        st[i + 1] = 0;
        st[i + n + 1] = 0;
        dr[i + 1] = 0;
        dr[i + n + 1] = 0;
        for (int j = 1; j <= n; j++)
        {
            if (d[i][j] <= x)
            {
                mc[1].push_back(i + 1);
                mc[i + 1].push_back(1);
                mc[i + 1].push_back(n + j + 1);
                mc[n + j + 1].push_back(i + 1);
                mc[n + j + 1].push_back(2 * n + 2);
                mc[2 * n + 2].push_back(n + j + 1);
                cap[i + 1][j + n + 1] = d[i][j];
                cap[j + n + 1][i + 1] = -d[i][j];
                cost[i + 1][j + n + 1] = 1;
                cost[1][i + 1] = 1;
                cost[j + n + 1][2 * n + 2] = 1;
            }
        }
    }
    bool ok = false;
    while (1)
    {
        for (int i = 1; i <= 2 * n + 2; i++)
        {
            viz[i] = 0;
        }
        ok = false;
        for (int i = 2; i <= n + 1; i++)
        {
            if (!st[i])
            {
                ok |= pairup(i);
            }
        }
        if (!ok)
        {
            break;
        }
    }
    int ct = 0;
    for (int i = 2; i <= n + 1; i++)
    {
        if (st[i] > 0)
        {
            ct++;
        }
    }
    return (ct == n);
}

int main ()
{
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> sld[i].first >> sld[i].second;
    }
    for (int i = 1; i <= n; i++)
    {
        in >> adp[i].first >> adp[i].second;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            d[i][j] = sqrt((sld[i].first - adp[j].first) * (sld[i].first - adp[j].first) + (sld[i].second - adp[j].second) * (sld[i].second - adp[j].second));
        }
    }
    double l = 0, r = 2000;
    while (r - l > 0.0001)
    {
        double m = (l + r) / 2;
        if (verif(m))
        {
            r = m;
        }
        else
        {
            l = m;
        }
    }
    out << r << " ";
    in.close();
    out.close();
    return 0;
}