Cod sursa(job #2628655)

Utilizator loraclorac lorac lorac Data 16 iunie 2020 19:16:38
Problema Adapost Scor 47
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.48 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
ifstream cin("adapost.in");
ofstream cout("adapost.out");
typedef long double ld;
vector<pair<int,ld> > vec[805];
vector<int> rev[805];
ld vx[805],vy[805];
int l[805],r[805];
int c[805][805];
int pred[805];
ld dist[805];
ld dist2(ld x1,ld y1,ld x2,ld y2)
{return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}
vector<ld> s;
queue<int> q;
bool inq[805];
bool ok[805];
ld inf;
int n;
bool path(int nod)
{
    if(ok[nod])
        return false;
    ok[nod]=true;
    for(int x:rev[nod])
    if(!l[x])
    {
        l[x]=nod;
        r[nod]=x;
        return true;
    }
    for(int x:rev[nod])
    if(path(l[x]))
    {
        l[x]=nod;
        r[nod]=x;
        return true;
    }
    return false;
}
bool verif(ld maxim)
{
    for(int i=1;i<=n;++i)
    {
        r[i]=l[i+n]=0;
        rev[i].clear();
        for(auto x:vec[i]) if(0<x.second and x.second<=maxim)
            rev[i].push_back(x.first);
    }
    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))
        {
            modif=true;
            ++cuplaj;
        }
    }while(modif);
    return (cuplaj==n);
}
ld rasp(ld maxim)
{
    for(int i=1;i<=n;++i)
    for(auto x:vec[i]) if(x.second<=maxim)
        c[i][x.first]=1;
    for(int i=1;i<=n;++i)
        c[0][i]=c[i+n][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(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 t=2*n+1;pred[t]>=0;t=pred[t])
                ads=min(ads,c[pred[t]][t]);
            if(ads<=0) continue;
            for(int t=2*n+1;pred[t]>=0;t=pred[t])
            {
                c[pred[t]][t]-=ads;
                c[t][pred[t]]+=ads;
            }
            cost+=dist[2*n+1];
        }
    }while(pred[2*n+1]>=0);
    return cost;
}
int main()
{
    ld x,y;
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>vx[i]>>vy[i];
    for(int j=n+1;j<=2*n;++j)
    {
        cin>>x>>y;
        for(int i=1;i<=n;++i)
        {
            ld cost=dist2(vx[i],vy[i],x,y);
            s.push_back(cost);
            vec[i].push_back({j,cost});
            vec[j].push_back({i,-cost});
        }
    }
    for(int i=1;i<=n;++i)
    {
        vec[0].push_back({i,0});
        vec[i].push_back({0,0});
    }
    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});
    }
    sort(s.begin(),s.end());
    inf=1.+s[s.size()-1];
    int l=0,r=s.size()-1,med;
    while(l<r)
    {
        med=(l+r)/2;
        if(verif(s[med]))
            r=med;
        else l=med+1;
    }
    cout<<fixed<<setprecision(6)<<s[l]<<' '<<rasp(s[l])<<'\n';
    return 0;
}