Pagini recente » Autentificare | Cod sursa (job #606416) | Cod sursa (job #1777190) | Cod sursa (job #1140643) | Cod sursa (job #2276525)
#include <bits/stdc++.h>
const double eps=1e-3;
const int oo=1e9;
const int N=410;
using namespace std;
//ifstream f("adapost.in");
//ofstream g("adapost.out");
int n,i,j,mi,lo,hi,poz[N][N],cap[2*N][2*N];
pair<double,double> sold[N],home[N];
vector<pair<double,pair<int,int> > > u;
double flow,cost[2*N][2*N],dist[2*N];
vector<int> v[2*N],fren[N];
bitset<N> viz;
int S[N],D[N];
bool grow(int poz)
{
if(viz[poz])return 0;
viz[poz]=1;
for(auto it:fren[poz])
if(!S[it])
{
S[it]=poz;
D[poz]=it;
return 1;
}
for(auto it:fren[poz])
if(grow(S[it]))
{
S[it]=poz;
D[poz]=it;
return 1;
}
return 0;
}
bool bipart(int mi)
{
for(int i=1;i<=n;i++)
S[i]=D[i]=0;
for(int i=1;i<=n;i++)
{
fren[i].resize(0);
for(j=1;j<=n;j++)
if(poz[i][j]<=mi)
fren[i].push_back(j);
}
int meci=0;
for(bool ok=1;ok;)
{
ok=0;viz.reset();
for(int i=1;i<=n;i++)
if((!D[i])&&grow(i))
{
ok=1;
meci++;
}
}
return (meci==n);
}
void bell()
{
queue<int> Q;
bitset<2*N> in;in.reset();
for(i=0;i<=2*n+1;i++)
dist[i]=oo;
dist[0]=0;Q.push(0);in[0]=1;
while(Q.size())
{
int x=Q.front();
Q.pop();in[x]=0;
for(auto it:v[x])
if(cap[x][it]&&(dist[it]-(dist[x]+cost[x][it])>eps))
{
dist[it]=dist[x]+cost[x][it];
if(!in[it])
Q.push(it);
in[it]=1;
}
}
}
bool dij()
{
priority_queue<pair<double,int> > Q;
int tata[2*N];
double new_d[2*N],real_d[2*N];
for(i=0;i<=2*n+1;i++)
real_d[i]=new_d[i]=tata[i]=oo;
real_d[0]=new_d[0]=tata[0]=0;
Q.push({0,0});
while(Q.size())
{
int x= Q.top().second;
double cst=-Q.top().first;
Q.pop();
// cout<<"JEF: "<<x<<'\n';
if(cst!=new_d[x])
continue;
for(auto it:v[x])
if(cap[x][it]&&(new_d[it]-(new_d[x]+cost[x][it]+dist[it]-dist[x])>eps))
{
// cout<<"ye: "<<it<<'\n';
new_d[it]=new_d[x]+cost[x][it]+dist[it]-dist[x];
Q.push({-new_d[it],it});
real_d[it]=real_d[x]+cost[x][it];
tata[it]=x;
}
// else
// cout<<"na: "<<it<<'\n';
}
// for(i=0;i<=2*n+1;i++)
// cout<<dist[i]<<' ';
// cout<<'\n';
for(i=0;i<=2*n+1;i++)
dist[i]=real_d[i];
// for(i=0;i<=2*n+1;i++)
// cout<<dist[i]<<' ';
// cout<<'\n';
// cout<<'\n';
if(dist[2*n+1]==oo)
return 0;
int flux=oo;
for(int nod=2*n+1;nod;nod=tata[nod])
flux=min(flux,cap[tata[nod]][nod]);
for(int nod=2*n+1;nod;nod=tata[nod])
{
cap[tata[nod]][nod]-=flux;
cap[nod][tata[nod]]+=flux;
}
flow+=dist[2*n+1]*(double)flux;
return 1;
}
int main()
{
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
// f>>n;
scanf("%d", &n);
for(i=1;i<=n;i++)
// f>>sold[i].first>>sold[i].second;
scanf("%lf%lf", &sold[i].first, &sold[i].second);
for(i=1;i<=n;i++)
// f>>home[i].first>>home[i].second;
scanf("%lf%lf", &home[i].first, &home[i].second);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cost[i][j+n]=sqrt((sold[i].first-home[j].first)*(sold[i].first-home[j].first)+
(sold[i].second-home[j].second)*(sold[i].second-home[j].second));
cost[j+n][i]=-cost[i][j+n];
u.push_back({cost[i][j+n],{i,j}});
v[i].push_back(j+n);
v[j+n].push_back(i);
}
u.push_back({0,{0,0}});
sort(u.begin(),u.end());
for(i=1;i<=n*n;i++)
poz[u[i].second.first][u[i].second.second]=i;
lo=1,hi=n*n;
while(lo<hi)
{
mi=(lo+hi)/2;
if(bipart(mi))
hi=mi;
else
lo=mi+1;
}
// for(i=1;i<=n*n;i++)
// cout<<bipart(i)<<' ';cout<<'\n';
// for(i=1;i<=n*n;i++)
// cout<<u[i].second.first<<' '<<u[i].second.second<<' '<<u[i].first<<'\n';
// cout<<lo<<'\n';
printf("%.4f ", u[lo].first);
// g<<fixed<<setprecision(5)<<u[lo].first<<' ';
for(i=1;i<=lo;i++)
cap[u[i].second.first][u[i].second.second+n]=N;
for(i=1;i<=n;i++)
{
cap[0][i]=1;
v[0].push_back(i);
}
for(i=n+1;i<=2*n;i++)
{
cap[i][2*n+1]=1;
v[i].push_back(2*n+1);
}
bell();
for(;dij(););
printf("%.4f ", flow);
// g<<fixed<<setprecision(5)<<flow;
return 0;
}