Cod sursa(job #2628771)

Utilizator loraclorac lorac lorac Data 17 iunie 2020 14:05:32
Problema Adapost Scor 61
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.32 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("adapost.in");
ofstream out("adapost.out");
typedef long double ld;
ld vx[405],vy[405];
vector<pair<int,ld> > vec[805];
ld dist2(ld x,ld y,ld xx,ld yy)
{
    return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));
}
vector<ld> d;
int l[805],r[805];
bool ok[805];
int n;
bool path(int nod,ld maxim)
{
    if(ok[nod])
        return false;
    ok[nod]=true;
    for(auto x:vec[nod])
    if(x.second<=maxim)
    if(!l[x.first])
    {
        r[nod]=x.first;
        l[x.first]=nod;
        return true;
    }
    for(auto x:vec[nod])
    if(x.second<=maxim)
    if(path(l[x.first],maxim))
    {
        r[nod]=x.first;
        l[x.first]=nod;
        return true;
    }
    return false;
}
bool verif(ld maxim)
{
    for(int i=1;i<=2*n;++i)
        l[i]=r[i]=0;
    bool modif;
    int cuplaj=0;
    do
    {
        for(int i=1;i<=n;++i)
            ok[i]=false;
        modif=false;
        for(int i=1;i<=n;++i)
        if(!r[i] and path(i,maxim))
        {
            modif=true;
            ++cuplaj;
        }
    }while(modif);
    return (cuplaj==n);
}
int c[805][805];
int pred[805];
ld dist[805];
queue<int> q;
ld inf;
bool inq[805];
ld rez(ld maxim)
{
    for(int i=1;i<=n;++i)
    {
        vec[0].push_back({i,0});
        vec[i].push_back({0,0});
        c[0][i]=1;
    }
    for(int i=n+1;i<=2*n;++i)
    {
        vec[i].push_back({2*n+1,0});
        vec[2*n+1].push_back({i,0});
        c[i][2*n+1]=1;
    }
    ld cost=0.;
    int ads;
    do
    {
        for(int i=1;i<=2*n+1;++i)
        {
            pred[i]=-1;
            dist[i]=inf;
        }
        pred[0]=-2;
        dist[0]=0.;
        q.push(0);
        inq[0]=true;
        while(!q.empty())
        {
            int x=q.front(); q.pop();
            inq[x]=false;
            for(auto y:vec[x])
            if(abs(y.second)<=maxim and c[x][y.first]>0 and dist[y.first]>dist[x]+y.second)
            {
                dist[y.first]=dist[x]+y.second;
                pred[y.first]=x;
                if(!inq[y.first]) inq[y.first]=true,q.push(y.first);
            }
        }
        if(pred[2*n+1]>=0)
        {
            ads=c[pred[2*n+1]][2*n+1];
            for(int k=pred[2*n+1];pred[k]>=0;k=pred[k])
                ads=min(ads,c[pred[k]][k]);
            if(ads<=0) continue;
            for(int k=2*n+1;pred[k]>=0;k=pred[k])
            {
                c[pred[k]][k]-=ads;
                c[k][pred[k]]+=ads;
            }
            cost+=1.*ads*dist[2*n+1];
        }
    }while(pred[2*n+1]>=0);
    return cost;
}
int main()
{
    in>>n;
    for(int i=1;i<=n;++i)
        in>>vx[i]>>vy[i];
    for(int j=n+1;j<=2*n;++j)
    {
        ld x,y;
        in>>x>>y;
        for(int i=1;i<=n;++i)
        {
            ld dd=dist2(vx[i],vy[i],x,y);
            d.push_back(dd);
            vec[i].push_back({j,dd});
            vec[j].push_back({i,-dd});
            c[i][j]=1;
        }
    }
    sort(d.begin(),d.end());
    int l=0,r=d.size()-1,med;
    inf=1.+d[r];
    while(l<r)
    {
        med=(l+r)/2;
        if(verif(d[med]))
            r=med;
        else l=med+1;
    }
    out<<fixed<<setprecision(5)<<d[l]<<' ';
    if(n<=160)
        out<<fixed<<setprecision(5)<<rez(d[l])<<'\n';
    return 0;
}