Pagini recente » Cod sursa (job #1194133) | Cod sursa (job #548107) | Cod sursa (job #1893402) | Cod sursa (job #1965295) | Cod sursa (job #2628655)
#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;
}