Cod sursa(job #3202815)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 12 februarie 2024 12:15:01
Problema Adapost Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <bits/stdc++.h>
#ifdef LOCAL
#define in cin
#define out cout
#endif

using namespace std;

#ifndef LOCAL
ifstream in("adapost.in");
ofstream out("adapost.out");
#endif

const int nmax = 405;
int n;
pair<double, double> p1[nmax], p2[nmax];

struct line
{
    int i, j;
    double dist;
    line(int i = 0, int j = 0) : i(i), j(j)
    {
        double x = abs(p1[i].first - p2[j].first);
        double y = abs(p1[i].second - p2[j].second);
        dist = sqrt(x * x + y * y);
    }
    bool operator<(const line &other)
    {
        return dist < other.dist;
    }
    void debug()
    {
        cerr << i << ' ' << j << ' ' << dist << '\n';
    }
} lines[nmax * nmax];

double biadj[nmax][nmax];
int l[nmax], r[nmax];
bool viz[nmax];

bool pairup(int nod, double upp)
{
    if (viz[nod])
        return 0;
    viz[nod] = 1;
    for (int i = 0; i < n; i++)
    {
        if (biadj[nod][i] <= upp)
        {
            if (l[i] == -1)
            {
                l[i] = nod;
                r[nod] = i;
                return 1;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (biadj[nod][i] <= upp)
        {
            if (pairup(l[i], upp))
            {
                l[i] = nod;
                r[nod] = i;
                return 1;
            }
        }
    }
    return 0;
}

bool bipart(double upperbound)
{
    for (int i = 0; i < n; i++)
    {
        l[i] = -1;
        r[i] = -1;
    }
    bool change = 0;
    int pairs = 0;
    do
    {
        change = 0;
        memset(viz, 0, sizeof viz);
        for (int i = 0; i < n; i++)
        {
            if (r[i] == -1)
            {
                if (pairup(i, upperbound))
                {
                    change = 1;
                    pairs++;
                }
            }
        }
    } while (change);
    return pairs == n;
}

int main()
{
    in >> n;
    for (int i = 0; i < n; i++)
    {
        in >> p1[i].first >> p1[i].second;
    }
    for (int i = 0; i < n; i++)
    {
        in >> p2[i].first >> p2[i].second;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            lines[i * (n) + j] = line(i, j);
            biadj[i][j] = lines[i * (n) + j].dist;
        }
    sort(lines, lines + (n * n));
    int st = 0, dr = n * n - 1;
    while (st < dr)
    {
        int mid = (st + dr) / 2;
        if (bipart(lines[mid].dist))
        {
            dr = mid;
        }
        else
        {
            st = mid + 1;
        }
    }
    double upp = lines[st].dist;
    out<<upp<<' ';
}