Pagini recente » Cod sursa (job #575042) | Cod sursa (job #2221798) | Cod sursa (job #90620) | Istoria paginii runda/crasfd | Cod sursa (job #1035769)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
vector<int> G[805];
double cost[805][805];
int C[805][805],F[805][805];
int p[805];double d[805];
struct Point {double x,y;} a[405],b[405];
inline bool cmp(int a,int b) {return d[a]>d[b];}
int Q[1000005];
int U[805];
bool BellmanFord()
{
for(int i=1;i<=2*n+1;i++)
{
d[i]=1000000000.0;
p[i]=-1;
}
int L=1;
d[0]=0;Q[L]=0;
memset(U,0,sizeof(U));
U[0]=1;
for(int i=1;i<=L;U[Q[i++]]=0)
for(vector<int>::iterator it=G[Q[i]].begin();it!=G[Q[i]].end();it++)
if(C[Q[i]][*it]-F[Q[i]][*it]>0 && d[Q[i]]+cost[Q[i]][*it]<d[*it])
{
d[*it]=d[Q[i]]+cost[Q[i]][*it];
p[*it]=Q[i];
if(!U[*it])
{
Q[++L]=*it;
U[Q[L]]=1;
}
}
if(d[2*n+1]<999999999.0)
return true;
return false;
}
double MaxFlowMinCost(double lim)
{
memset(F,0,sizeof(F));
for(int i=0;i<=2*n+1;i++)
G[i].clear();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(cost[i][j+n]<=lim)
{
G[i].push_back(n+j);
G[n+j].push_back(i);
}
for(int i=1;i<=n;i++)
{
G[0].push_back(i);
G[i].push_back(0);
G[n+i].push_back(2*n+1);
G[2*n+1].push_back(n+i);
}
int total=0;double tc=0;
while(BellmanFord())
{
int u=2*n+1,flux=1000000000;
while(u!=0)
{
flux=min(flux,C[p[u]][u]-F[p[u]][u]);
u=p[u];
}
u=2*n+1;
while(u!=0)
{
F[p[u]][u]+=flux;
F[u][p[u]]-=flux;
u=p[u];
}
total+=flux;
tc+=d[2*n+1]*flux;
}
if(total!=n)
return -1.0;
return tc;
}
int main()
{
freopen("adapost.in","r",stdin);
freopen("adapost.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&b[i].x,&b[i].y);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cost[i][j+n]=sqrt((a[i].x-b[j].x)*(a[i].x-b[j].x)+(a[i].y-b[j].y)*(a[i].y-b[j].y));
cost[j+n][i]=-cost[i][j+n];
C[i][j+n]=1;
}
for(int i=1;i<=n;i++)
C[0][i]=C[i+n][2*n+1]=1;
double st,dr,med,last,last_pd;
st=0;dr=10000.0;last=dr;
while(dr-st>0.0001)
{
med=(st+dr)*0.5;
double pd=MaxFlowMinCost(med);
if(pd<0)
st=med+0.0001;
else
{
last=med;last_pd=pd;
dr=med-0.0001;
}
}
printf("%.5lf %.5lf\n",last,last_pd);
return 0;
}