Cod sursa(job #1871992)

Utilizator borcanirobertBorcani Robert borcanirobert Data 7 februarie 2017 20:44:11
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

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

const int MAX = 2*405;
const int Inf = 0x3f3f3f3f;
const double eps = 0.0001;
struct Nod{
    int nod, cost;

    bool operator < ( const Nod& a )
    {
        return cost > a.cost;
    }
};
using VI = vector<int>;
using VF = vector<double>;
vector<int> G[MAX];
VI l, r, u;
vector<pair<double, double>> s, a;
int n, N;
double d[MAX][MAX];
double dmax;
VF dist;

void ReadAndBuildGraph();
bool PairUp( int x );
bool Verif( int ld );
double Minim();

int main()
{
    ReadAndBuildGraph();

    fout << Minim() << ' ';

    fin.close();
    fout.close();
    return 0;
}

void ReadAndBuildGraph()
{
    int x, y;
    fin >> n; N = 2*n + 1;
    s = a = vector<pair<double, double>>(n + 1);

    for ( int i = 1; i <= n; ++i )
        fin >> s[i].first >> s[i].second;

    for ( int i = 1; i <= n; ++i )
        fin >> a[i].first >> a[i].second;

    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= n; ++j )
        {
            d[i][j] = sqrt( (a[j].first - s[i].first)*(a[j].first - s[i].first) + (a[j].second - s[i].second)*(a[j].second - s[i].second) );
            dist.push_back(d[i][j]);
            G[i].push_back(j + n);
            G[j + n].push_back(i);
        }
    sort( dist.begin(), dist.end() );
}

bool PairUp( int x )
{
    if ( u[x] ) return false;
    u[x] = 1;

    for ( int i = 1; i <= n; ++i )
    {
        if ( !r[i] && d[x][i] - dmax <= eps )
        {
            l[x] = i;
            r[i] = x;
            return true;
        }
    }

    for ( int i = 1; i <= n; ++i )
        if ( d[x][i] - dmax <= eps )
            if ( PairUp(r[i]) )
            {
                l[x] = i;
                r[i] = x;
                return true;
            }

    return false;
}

bool Verif( int ld )
{
    dmax = dist[ld];
    bool change;

    l = r = VI(n + 1);

    do
    {
        change = false;
        u = VI(n + 1, 0);
        for ( int i = 1; i <= n; ++i )
            if ( !l[i] )
                change |= PairUp(i);
    }while ( change );

    for ( int i = 1; i <= n; ++i )
        if ( !l[i] )
            return false;
    return true;
}

double Minim()
{
    int st = 0, dr = dist.size() - 1, mij;
    double rez;

    while ( st <= dr )
    {
        mij = ( st + dr ) / 2;

        if ( Verif(mij) )
        {
            dr = mij - 1;
            rez = dist[mij];
        }
        else
            st = mij + 1;
    }

    return rez;
}