Pagini recente » Cod sursa (job #3262990) | Cod sursa (job #2683613) | Cod sursa (job #2466228) | Cod sursa (job #336685) | Cod sursa (job #2448003)
#include <bits/stdc++.h>
#define pdd pair<double, double>
#define pdi pair<double, int>
#define inf 1000000000
///N=400
using namespace std;
///
int n, i, j, k, s, d, cnt, l, r, mid;
int flow[801][801], last[801];
double outone, outall;
double cost[801][801], dlist[16001], dmin[801], now[801], then[801];
pdd plist[801];
vector<int> graph[805];
priority_queue<pdi, vector<pdi>, greater<pdi> > pq;
///
void read();
void solve();
void write();
double calc(pdd node1, pdd node2);
bool doflow(double val);
bool dij(double val);
int main()
{
read();
solve();
write();
return 0;
}
void read(){
freopen("adapost.in", "r", stdin);
scanf("%d", &n);
for(i=1; i<=2*n; ++i) scanf("%lf%lf", &plist[i].first, &plist[i].second);
fclose(stdin);
return;
}
void solve(){
s=0, d=2*n+1;
for(i=1; i<=n; ++i)
for(j=n+1; j<=2*n; ++j){
double dist=calc(plist[i], plist[j]);
cost[i][j]=dist;
cost[j][i]=-dist;
flow[i][j]=1;
dlist[++cnt]=dist;
graph[i].push_back(j);
graph[j].push_back(i);
}
for(i=1; i<=n; ++i) {
flow[s][i]=1;
graph[s].push_back(i);
graph[i].push_back(s);
}
for(i=n+1; i<=2*n; ++i) {
flow[i][d]=1;
graph[i].push_back(d);
graph[d].push_back(i);
}
sort(dlist+1, dlist+n*n+1);
l=1; r=n*n;
while(l<=r){
mid=(l+r)/2;
if(doflow(dlist[mid])) r=mid-1;
else l=mid+1;
}
return;
}
void write(){
freopen("adapost.out", "w", stdout);
printf("%fl %fl", outone, outall);
return;
}
double calc(pdd node1, pdd node2){
return sqrt((node1.first-node2.first)*(node1.first-node2.first)+(node1.second-node2.second)*(node1.second-node2.second));
}
bool doflow(double val){
for(i=s; i<=d; ++i) then[i]=now[i]=0.0;
for(i=1; i<=n; ++i) for(j=n+1; j<=2*n; ++j) flow[i][j]=1;
for(i=1; i<=n; ++i) {flow[s][i]=1; flow[i][s]=0;}
for(i=n+1; i<=2*n; ++i) {flow[i][d]=1; flow[d][i]=0;}
double sol=0;
while(dij(val)){
int p, maxflow=inf;
for(p=d; p!=s; p=last[p]) maxflow=min(maxflow, flow[last[p]][p]);
for(p=d; p!=s; p=last[p]){
flow[last[p]][p]-=maxflow;
flow[p][last[p]]+=maxflow;
sol+=cost[last[p]][p];
}
}
int done=0;
for(i=1; i<=n; ++i)
for(j=n+1; j<=2*n; ++j) if(!flow[i][j]){++done; break;}
if(done==n){outone=val; outall=sol;}
return done==n;
}
bool dij(double val){
for(i=s; i<=d; ++i) last[i]=-1, dmin[i]=inf;
dmin[s]=now[s]=0.0;
pq.push({0, s});
while(!pq.empty()){
double cst=pq.top().first;
int node=pq.top().second;
pq.pop();
if(node==d) continue;
if(cst>dmin[node]) continue;
for(auto next:graph[node]){
if(!flow[node][next]) continue;
if(cost[node][next]>val) continue;
double nextc=cst+cost[node][next]+then[node]-then[next];
if(nextc<dmin[next]){
dmin[next]=nextc;
now[next]=now[node]+cost[node][next];
last[next]=node;
pq.push({nextc, next});
}
}
}
for(i=s; i<=d; ++i) then[i]=now[i];
return dmin[d]!=inf;
}