Cod sursa(job #16736)

Utilizator victorsbVictor Rusu victorsb Data 13 februarie 2007 22:23:44
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define Nmax 405
#define x first
#define y second
#define pb push_back
#define sz size()

int n;
const double eps = 0.0000001;
int v[Nmax], dest[Nmax], p[Nmax];
pair<double, double> s[Nmax], a[Nmax];
double dist[Nmax*Nmax], c[Nmax][Nmax];
vector<int> lv[Nmax];

void citire()
{
    int i;
    scanf("%d\n", &n);
    for (i=1; i<=n; ++i)
        scanf("%lf %lf\n", &s[i].x, &s[i].y);
    for (i=1; i<=n; ++i)
        scanf("%lf %lf\n", &a[i].x, &a[i].y);
}

double dst(int p1, int p2)
{
    return sqrt(pow(s[p1].x - a[p2].x, 2) + pow(s[p1].y - a[p2].y, 2));
}

int cupleaza(int nod)
{
    int i;
    v[nod] = 1;
    for (i=0; i<lv[nod].sz; ++i)
        if (!dest[lv[nod][i]])
        {
            dest[lv[nod][i]] = nod;
            p[nod] = lv[nod][i];
            return 1;
        }
    for (i=0; i<lv[nod].sz; ++i)
        if (!v[dest[lv[nod][i]]])
            if (cupleaza(dest[lv[nod][i]]))
            {
                dest[lv[nod][i]] = nod;
                p[nod] = lv[nod][i];
                return 1;
            }
    return 0;
}

int merge(double dist)
{
    int i, j, flux = 0, ok;
    memset(dest, 0, sizeof(dest));
    memset(p, 0, sizeof(p));
    for (i=1; i<=n; ++i)
    {
        lv[i].clear();
        for (j=1; j<=n; ++j)
            if (c[i][j] + eps <= dist)
                lv[i].pb(j);
    }
    ok = 1;
    while (ok)
    {
        ok = 0;
        memset(v, 0, sizeof(v));
        for (i=1; i<=n; ++i)
            if (!p[i])
                if (cupleaza(i))
                {
                    ++flux;
                    ok = 1;
                }
    }
    if (flux == n)
        return 1;
    return 0;
}

void solve()
{
    int st, dr, mij, i, j, sol;
    st = 1;
    dr = 0;
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j)
            c[i][j] = dist[++dr] = dst(i, j);
    sort(dist+1, dist+dr+1);
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (merge(dist[mij]))
        {
            sol = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    printf("%.5lf 0\n", dist[sol]);
}

int main()
{
    freopen("adapost.in", "r", stdin);
    freopen("adapost.out", "w", stdout);
    citire();
    solve();
    return 0;
}