Cod sursa(job #2628848)

Utilizator betybety bety bety Data 17 iunie 2020 18:52:38
Problema Adapost Scor 63
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.55 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("adapost.in");
ofstream g("adapost.out");
vector<pair<int,long double> > vec[805];
vector<int> rev[805];
long double vx[805],vy[805];
int l[805],r[805];
int c[805][805];
int pred[805];
long double dist[805];
long double dist2(long double x1,long double y1,long double x2,long double y2)
{return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}
vector<long double> s;
queue<int> q;
bool inq[805];
bool ok[805];
long double 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(long double 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);
}
long double rasp(long double 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;
    long double 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()
{
    long double x,y;
    f>>n;
    for(int i=1;i<=n;++i)
        f>>vx[i]>>vy[i];
    for(int j=n+1;j<=2*n;++j)
    {
        f>>x>>y;
        for(int i=1;i<=n;++i)
        {
            long double 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;
    }
    g<<fixed<<setprecision(5)<<s[l]<<' ';
    if(n<=250)
        g<<fixed<<setprecision(5)<<rasp(s[l])<<'\n';
    return 0;
}