Pagini recente » Cod sursa (job #1430771) | Cod sursa (job #2589360) | Cod sursa (job #512564) | Cod sursa (job #1387460) | Cod sursa (job #2276350)
#include <bits/stdc++.h>
const long double eps=1e-5;
const int oo=1e9;
using namespace std;
ifstream f("adapost.in");
ofstream g("adapost.out");
int n,i,j,flow,cap[410][410];
long double ans,lo,hi,x[410],y[410],adx[410],ady[410],cost[410][410];
vector<int> v[1010];
bool bell()
{
queue<int> Q;
long double dist[410];int tata[410];
bitset<410> in;in.reset();
for(i=0;i<=2*n+1;i++)
dist[i]=oo,tata[i]=-1;
dist[0]=0;Q.push(0);
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]))
{
dist[it]=dist[x]+cost[x][it];
if(!in[it])
Q.push(it);
in[it]=0;
tata[it]=x;
}
}
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+=flux;
ans+=dist[2*n+1]*(long double)flux;
return 1;
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>x[i]>>y[i];
for(i=1;i<=n;i++)
f>>adx[i]>>ady[i];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
v[i].push_back(n+j);
v[n+j].push_back(i);
cost[i][n+j]=sqrt((x[i]-adx[j])*(x[i]-adx[j])+(y[i]-ady[j])*(y[i]-ady[j]));
cost[n+j][i]=-cost[i][n+j];
}
lo=0,hi=2000;
for(i=1;i<=n;i++)
v[0].push_back(i);
for(j=n+1;j<=2*n;j++)
v[j].push_back(2*n+1);
while(hi-lo>eps)
{
long double mi=(lo+hi)/2;
for(i=0;i<=2*n+1;i++)
for(j=0;j<=2*n+1;j++)
cap[i][j]=0;
for(i=1;i<=n;i++)
cap[0][i]=1;
for(j=n+1;j<=2*n;j++)
cap[j][2*n+1]=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(mi-cost[i][n+j]>eps)
cap[i][n+j]=oo;
ans=0;flow=0;
for(;bell(););
//cout<<mi<<' '<<flow<<' '<<ans<<'\n';
if(flow==n)
hi=mi;
else
lo=mi;
}
for(i=0;i<=2*n+1;i++)
for(j=0;j<=2*n+1;j++)
cap[i][j]=0;
for(i=1;i<=n;i++)
cap[0][i]=1;
for(j=n+1;j<=2*n;j++)
cap[j][2*n+1]=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(hi-cost[i][n+j]>eps)
cap[i][n+j]=oo;
ans=0;
for(;bell(););
g<<fixed<<setprecision(4)<<hi<<' '<<ans;
return 0;
}