Cod sursa(job #3033201)

Utilizator Zed1YasuoAlex Birsan Zed1Yasuo Data 23 martie 2023 15:39:12
Problema Adapost Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.15 kb
#include <fstream>
#define D double
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#define esp 1e-3
#include <iomanip>
using namespace std;
ifstream f("adapost.in");
ofstream g("adapost.out");
int n,m,ANS,st,dr;
const int N=805;
struct pct
{
    D x,y;
} v[N],r[N];
vector<int>a[N];
D get_dist(pct A,pct B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
int flux[N][N];
D d[N][N];
D dist[N];
bool viz[N];
int dad[N];
int niv[N],fr[N];
D ford(int st,int dr,D MIJ)
{
    for(int i=st; i<=dr; i++)
    {
        dist[i]=1e9;
        dad[i]=0;
        viz[i]=false;
    }
    queue<int>q;
    dist[st]=0;
    q.push(st);
    viz[st]=true;
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        viz[nod]=false;
        for(auto x: a[nod])
        {
            if(dist[x]>dist[nod]+d[nod][x]&&flux[nod][x]>0)
            {
                dist[x]=dist[nod]+d[nod][x];
                dad[x]=nod;
                if(viz[x]==false)
                {
                    viz[x]=true;
                    q.push(x);
                }
            }
        }
    }
    return dist[dr];
}
D get_flux(D lat)
{
    D vall=0;
    while(true)
    {
        D sol=ford(st,dr,lat);
        if(sol==1e9)
            break;
        for(int i=dr; i!=st; i=dad[i])
        {
            flux[dad[i]][i]--;
            flux[i][dad[i]]++;
        }
        vall=vall+sol;
    }
    return vall;
}
void reset(D mij)
{
    for(int i=0; i<=dr; i++)
        a[i].clear();
    for(int i=1; i<=n; i++)
        for(int j=n+1; j<=2*n; j++)
            flux[i][j]=0,flux[j][i]=0;
    for(int i=1; i<=n; i++)
        flux[st][i]=1,flux[i+n][dr]=1;
    ///adaugam muchiile pana la MIJ
    for(int i=1; i<=n; i++)
        for(int j=n+1; j<=2*n; j++)
        {
            if(d[i][j]<=mij)
            {
                a[i].push_back(j);
                a[j].push_back(i);
                flux[i][j]=1;
            }
        }
    for(int i=1; i<=n; i++)
    {
        a[st].push_back(i);
        a[i].push_back(st);
        a[i+n].push_back(dr);
        a[dr].push_back(i+n);
    }
}
void bfs(int nod)
{
    for(int i=0; i<=dr; i++)
        niv[i]=-1,fr[i]=0;
    niv[nod]=0;
    queue<int>q;
    q.push(nod);
    while(!q.empty())
    {
        int next=q.front();
        q.pop();
        for(auto x : a[next])
            if(niv[x]==-1&&flux[next][x]>0)
            {
                niv[x]=niv[next]+1;
                q.push(x);
            }
    }
}
int dfs(int nod,int mn)
{
    if(nod==dr||mn==0)
        return mn;
    while(fr[nod]<a[nod].size())
    {
        int x=a[nod][fr[nod]];
        fr[nod]++;
        if(flux[nod][x]>0&&niv[x]==niv[nod]+1)
        {
            int R=dfs(x,min(flux[nod][x],mn));
            if(R>0)
            {
                flux[nod][x]-=R;
                flux[x][nod]+=R;
                return R;
            }
        }
    }
}
bool ver()
{
    bfs(st);
    if(niv[dr]==-1)
        return 0;
    else
    {
        int AL=0;
        while(true)
        {
            int x=dfs(st,1e9);
            if(x==0)
                break;
            else
                AL+=x;
        }
        ANS+=AL;
        if(AL==0)
            return false;
        return true;
    }
}
bool flx(D mij)
{
    reset(mij);
    ANS=0;
    while(ver());
    if(ANS==n)
        return true;
    return false;
}
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>v[i].x>>v[i].y;
    for(int i=1; i<=n; i++)
        f>>r[i].x>>r[i].y;
    st=0;
    dr=2*n+1;
    ///muchie st - i,  i+n dr
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {

            flux[i][j+n]=1;
            D dd=get_dist(v[i],r[j]);
            d[i][j+n]=dd;
            d[j+n][i]=-dd;

        }
    D st=0,dr=1500;
    D RE;
    while(dr-st>esp)
    {
        D mj=(st+dr)/2;
        if(flx(mj))
            dr=mj;
        else
            st=mj;
    }
    reset(dr);
    RE=get_flux(dr);
    g<<fixed<<setprecision(6)<<dr<<" ";
    g<<fixed<<setprecision(6)<<RE;
    return 0;
}