Cod sursa(job #402318)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 23 februarie 2010 19:26:05
Problema Adapost Scor 2
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#define Nmx 405
#define INF 1000001

using namespace std;

struct coord{ double x,y;};
int n,nr,Q[Nmx*Nmx*10],st,dr,viz[Nmx*2],prec[Nmx*2];
int C[Nmx*2][Nmx*2],F[Nmx*2][Nmx*2],r[Nmx*2],l[Nmx*2];
coord a[Nmx],b[Nmx];
double c[Nmx],cost[Nmx*2];
vector<pair< int,double > > G[Nmx];
double dist(double x,double y,double x1,double y1)
{
    return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}

void citire()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lf%lf",&a[i].x,&a[i].y);
    for(int i=1;i<=n;++i)
        scanf("%lf%lf",&b[i].x,&b[i].y);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            c[++nr]=dist(a[i].x,a[i].y,b[i].x,b[i].y);
            C[i][j+n]=C[0][i]=C[j+n][n+n+1]=1;
            G[i].push_back(make_pair(j+n,c[nr]));
            G[j+n].push_back(make_pair(i,-c[nr]));
            G[0].push_back(make_pair(i,0));
            G[j+n].push_back(make_pair(n+n+1,0));
        }
    sort(c+1,c+nr+1);
}

int pairup (int nod,double x)
{
    vector< pair <int,double> >:: iterator it;
    int i;
    if (viz[nod])
        return 0;
    viz[nod]=1;
    for (it=G[nod].begin();it!=G[nod].end(); ++it)
        if (it->second<=x&&!r[it->first])
        {
            r[it->first]=nod;
            l[nod]=it->first;
            return 1;
        }
    for (it=G[nod].begin();it!=G[nod].end(); ++it)
        if (pairup (r[it->first],x))
        {
            l[nod]=it->first;
            r[it->first]=nod;
            return 1;
        }
    return 0;
}

int este(double x)
{
    for(int i=0;i<=n+n;++i)
    for(int j=0;j<=n+n;++j)
        F[i][j]=0;
    int i,ok,cupl=0;
    do
    {
        ok=0;
        memset(viz,0,sizeof (viz));
        for (i=1; i<=n; ++i)
            if (!l[i] && pairup (i,x))
            {
                ++cupl;
                ok=1;
            }
    }
    while (ok);
    if(cupl!=n)
        return 0;
    return 1;
}

void solve()
{
    int st=1,dr=nr;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(este(c[mij]))
            dr=mij-1;
        else st=mij+1;
    }
    printf("%lf ",c[st]);
}

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