Cod sursa(job #3151917)

Utilizator Luca529Taschina Luca Luca529 Data 23 septembrie 2023 09:09:35
Problema Adapost Scor 6
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <iomanip>

using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
vector<int> x[1001];
pair<int, long double> h[1001][1001], h1[1001][1001];
long double v[1001][3], dist[1001], cost;
int n, nr, cuplat[1001], p[1001], prec[1001];

long double Dist(long double a, long double b, long double c, long double d)
{
    long double v=sqrt((c-a)*(c-a)+(d-b)*(d-b));
    return v;
}

void update(int a)
{while(prec[a]!=-1)
 {h[prec[a]][a].first--, cost+=h1[prec[a]][a].second;
  h[a][prec[a]].first++, cost-=h1[a][prec[a]].second;

  if(a>n && a!=nr)cuplat[a]=1;
  a=prec[a];
 }
}

struct Data{
int a;

bool operator <(const Data& other) const
{
    return dist[a]>dist[other.a];
}

};

bool CM(long double v)
{int a;
 cost=0;

 for(int i=0;i<=nr;i++)
 dist[i]=1e6, p[i]=0;
 prec[0]=-1, dist[0]=0;

 for(int i=n+1;i<nr;i++)
 cuplat[i]=0;

 for(int i=0;i<=nr;i++)
 for(int j=0;j<=nr;j++)
 h[i][j]=h1[i][j];

 vector<int>:: iterator I;
 queue<int> q;
 p[0]=1, q.push(0);

 while(q.empty()!=1)
 {a=q.front();
  p[a]=0;

  for(I=x[a].begin();I<x[a].end();I++)
  if(h[a][*I].first>0 && dist[*I]>dist[a]+h[a][*I].second && h1[a][*I].second<=v)
  {dist[*I]=dist[a]+h[a][*I].second, prec[*I]=a;
   if(p[*I]==0)p[*I]=1, q.push(*I);
  }
  q.pop();
 }

 if(dist[nr]!=1e6)
 {update(nr);

  for(int i=0;i<=nr;i++)
  for(I=x[i].begin();I<x[i].end();I++)
  h[i][*I].second+=dist[i]-dist[*I];
 }
 priority_queue<Data> q1;

 while(dist[nr]!=1e6)
 {for(int i=0;i<=nr;i++)
  dist[i]=1e6, p[i]=0;
  prec[0]=-1, dist[0]=0;

  q1.push({0}), p[0]=1;

  while(q1.empty()!=1)
  {a=q1.top().a;
   p[a]=0;

   for(I=x[a].begin();I<x[a].end();I++)
   if(h[a][*I].first>0 && dist[*I]>dist[a]+h[a][*I].second && h1[a][*I].second<=v)
   {dist[*I]=dist[a]+h[a][*I].second, prec[*I]=a;
    if(p[*I]==0)p[*I]=1, q1.push({*I});
   }
   q1.pop();
  }

  if(dist[nr]!=1e6)
  {update(nr);

   for(int i=0;i<=nr;i++)
   for(I=x[i].begin();I<x[i].end();I++)
   h[i][*I].second+=dist[i]-dist[*I];
  }
 }

 bool t=1;
 for(int i=1+n;i<nr && t;i++)
 if(cuplat[i]==0)t=0;

 return t;
}

int main()
{   long double mini=0, sol=0;
    fin>>n;
    nr=n*2+1;
    for(int i=1;i<=n;i++)
    {x[0].push_back(i);
     x[i].push_back(0);

     h1[0][i]={1, 0};
     h1[i][0]={0, 0};
    }

    for(int i=1;i<=n;i++)
    {x[nr].push_back(i+n);
     x[i+n].push_back(nr);

     h1[i+n][nr]={1, 0};
     h1[nr][i+n]={0, 0};
    }

    for(int i=1;i<=n*2;i++)
    fin>>v[i][1]>>v[i][2];

    for(int i=1;i<=n;i++)
    for(int j=n+1;j<nr;j++)
    {x[i].push_back(j);
     x[j].push_back(i);

     h1[i][j]={1, Dist(v[i][1], v[i][2], v[j][1], v[j][2])};
     h1[j][i]={0, -Dist(v[i][1], v[i][2], v[j][1], v[j][2])};
    }

    long double st=0, dr=100000, mij, v;

    while(st<=dr)
    {mij=(st+dr)/2;

     v=CM(mij);

     if(v==0)st=mij+0.00001;
     else mini=mij, sol=cost, dr=mij-0.00001;
    }

    fout<<fixed<<setprecision(3)<<mini<<" "<<sol;
    return 0;
}