Pagini recente » Cod sursa (job #2053200) | Cod sursa (job #2966909) | Cod sursa (job #2904644) | Cod sursa (job #2894466) | Cod sursa (job #1891391)
#include <bits/stdc++.h>
#define MAXN 1000
#define MAXQ (1<<17)
#define INF 1000000000
#define x first
#define y second
std::pair <double,double> A[MAXN+1];
std::pair <double,double> B[MAXN+1];
double v[MAXN*MAXN+1];
inline double Dist(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
std::vector <int> G[MAXN+1];
double cost[MAXN+1][MAXN+1];
int flow[MAXN+1][MAXN+1];
int cap[MAXN+1][MAXN+1];
int from[MAXN+1];
int Q[MAXQ];
double best[MAXN+1];
bool inQ[MAXN+1];
bool viz[MAXN+1];
int n;
inline void add(int &x){
x++;
x&=(MAXQ-1);
}
inline bool BellmanFord(int s,int d,double dist){
int b=0,e=1;
memset(from,0,sizeof(from));
memset(viz,0,sizeof(viz));
best[0]=0;
for(int i=1;i<=2*n+1;i++)
best[i]=INF;
Q[0]=s;
viz[s]=1;
inQ[s]=1;
while(b!=e){
int nod=Q[b];
inQ[nod]=0;
add(b);
for(int i=0;i<G[nod].size();i++){
int x=G[nod][i];
if(cap[nod][x]>flow[nod][x]&&cost[nod][x]<=dist&&best[x]>best[nod]+cost[nod][x]){
best[x]=best[nod]+cost[nod][x];
from[x]=nod;
if(!inQ[x]){
inQ[x]=1;
Q[e]=x;
viz[x]=1;
add(e);
}
}
}
}
return viz[d];
}
double ans;
inline int MaxFlow(double dist){
int flux=0;
ans=0;
memset(flow,0,sizeof(flow));
while(BellmanFord(0,2*n+1,dist)){
int min=INF;
int nod=2*n+1;
while(nod!=0){
if(min>cap[from[nod]][nod]-flow[from[nod]][nod])
min=cap[from[nod]][nod]-flow[from[nod]][nod];
nod=from[nod];
}
nod=2*n+1;
while(nod!=0){
flow[from[nod]][nod]+=min;
flow[nod][from[nod]]-=min;
ans+=1.0*min*cost[from[nod]][nod];
nod=from[nod];
}
flux+=min;
}
return flux;
}
int main(){
FILE*fi,*fout;
int i,j;
fi=fopen("adapost.in" ,"r");
fout=fopen("adapost.out" ,"w");
fscanf(fi,"%d " ,&n);
for(i=1;i<=n;i++)
fscanf(fi,"%lf %lf " ,&A[i].x,&A[i].y);
for(i=1;i<=n;i++)
fscanf(fi,"%lf %lf " ,&B[i].x,&B[i].y);
int m=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
cost[i][j+n]=Dist(A[i].x,A[i].y,B[j].x,B[j].y);
cost[j+n][i]=-cost[i][j+n];
cap[i][j+n]=1;
cap[j+n][i]=0;
G[i].push_back(j+n);
G[j+n].push_back(i);
v[++m]=cost[i][j+n];
}
for(i=1;i<=n;i++){
G[0].push_back(i);
G[i].push_back(0);
cap[0][i]=1;
cost[0][i]=0;
}
for(i=n+1;i<=2*n;i++){
G[i].push_back(2*n+1);
G[2*n+1].push_back(0);
cap[i][2*n+1]=1;
cost[i][2*n+1]=0;
}
std::sort(v+1,v+m+1);
int cnt=MaxFlow(v[m]);
int rez=0;
for(int pas=1<<14;pas;pas>>=1)
if(rez+pas<=m&&MaxFlow(v[rez+pas])<cnt)
rez+=pas;
MaxFlow(v[rez+1]);
fprintf(fout,"%lf %lf" ,v[rez+1],ans);
fclose(fi);
fclose(fout);
return 0;
}