Pagini recente » Cod sursa (job #2509655) | Cod sursa (job #148243) | Cod sursa (job #447850) | Cod sursa (job #3203678) | Cod sursa (job #2628771)
#include <bits/stdc++.h>
using namespace std;
ifstream in("adapost.in");
ofstream out("adapost.out");
typedef long double ld;
ld vx[405],vy[405];
vector<pair<int,ld> > vec[805];
ld dist2(ld x,ld y,ld xx,ld yy)
{
return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));
}
vector<ld> d;
int l[805],r[805];
bool ok[805];
int n;
bool path(int nod,ld maxim)
{
if(ok[nod])
return false;
ok[nod]=true;
for(auto x:vec[nod])
if(x.second<=maxim)
if(!l[x.first])
{
r[nod]=x.first;
l[x.first]=nod;
return true;
}
for(auto x:vec[nod])
if(x.second<=maxim)
if(path(l[x.first],maxim))
{
r[nod]=x.first;
l[x.first]=nod;
return true;
}
return false;
}
bool verif(ld maxim)
{
for(int i=1;i<=2*n;++i)
l[i]=r[i]=0;
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,maxim))
{
modif=true;
++cuplaj;
}
}while(modif);
return (cuplaj==n);
}
int c[805][805];
int pred[805];
ld dist[805];
queue<int> q;
ld inf;
bool inq[805];
ld rez(ld maxim)
{
for(int i=1;i<=n;++i)
{
vec[0].push_back({i,0});
vec[i].push_back({0,0});
c[0][i]=1;
}
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});
c[i][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(abs(y.second)<=maxim and 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 k=pred[2*n+1];pred[k]>=0;k=pred[k])
ads=min(ads,c[pred[k]][k]);
if(ads<=0) continue;
for(int k=2*n+1;pred[k]>=0;k=pred[k])
{
c[pred[k]][k]-=ads;
c[k][pred[k]]+=ads;
}
cost+=1.*ads*dist[2*n+1];
}
}while(pred[2*n+1]>=0);
return cost;
}
int main()
{
in>>n;
for(int i=1;i<=n;++i)
in>>vx[i]>>vy[i];
for(int j=n+1;j<=2*n;++j)
{
ld x,y;
in>>x>>y;
for(int i=1;i<=n;++i)
{
ld dd=dist2(vx[i],vy[i],x,y);
d.push_back(dd);
vec[i].push_back({j,dd});
vec[j].push_back({i,-dd});
c[i][j]=1;
}
}
sort(d.begin(),d.end());
int l=0,r=d.size()-1,med;
inf=1.+d[r];
while(l<r)
{
med=(l+r)/2;
if(verif(d[med]))
r=med;
else l=med+1;
}
out<<fixed<<setprecision(5)<<d[l]<<' ';
if(n<=160)
out<<fixed<<setprecision(5)<<rez(d[l])<<'\n';
return 0;
}