Pagini recente » Cod sursa (job #455548) | Cod sursa (job #3163800) | Cod sursa (job #2989197) | Cod sursa (job #1493528) | Cod sursa (job #2448097)
#include <bits/stdc++.h>
#define pdd pair<double, double>
#define pdi pair<double, int>
#define pii pair<int, 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];
bool inq[805];
double outone, outall;
double cost[801][801], dmin[801];
pdd plist[801];
pair<double, pii> dlist[801];
vector<int> graph[805];
queue<int> q;
///
void read();
void solve();
void write();
int CM();
bool dfs(int node);
bool refresh(int ind, bool ult);
void addedge(int i, int j, double c);
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){
pdd node1=plist[i], node2=plist[j];
double dist=sqrt((node1.first-node2.first)*(node1.first-node2.first)+(node1.second-node2.second)*(node1.second-node2.second));
dlist[++cnt].first=dist;
dlist[cnt].second={i, j};
}
sort(dlist+1, dlist+n*n+1);
l=1; r=n*n;
while(r-l>1){
mid=(l+r)/2;
if(refresh(mid, false)) r=mid;
else l=mid;
}
refresh(r, true);
outone=dlist[r].first;
while(true){
for(i=s; i<=d; ++i) last[i]=-1, dmin[i]=inf, inq[i]=false;
dmin[s]=0.0;
q.push(s); inq[s]=true;
while(!q.empty()){
int node=q.front(); q.pop(); inq[node]=false;
if(node==d) continue;
for(auto next:graph[node]){
if(!flow[node][next]) continue;
double nextc=dmin[node]+cost[node][next];
if(nextc<dmin[next]){
dmin[next]=nextc;
last[next]=node;
if(!inq[next]){
q.push(next);
inq[next]=true;
}
}
}
}
if(dmin[d]==inf) break;
int p;
for(p=d; p!=s; p=last[p]){
--flow[last[p]][p];
++flow[p][last[p]];
outall+=cost[last[p]][p];
}
}
return;
}
void write(){
freopen("adapost.out", "w", stdout);
printf("%.5f %.5f", outone, outall);
return;
}
int CM(){
for(i=1; i<=2*n; ++i) dmin[i]=last[i]=0;
bool done; int nr=0;
do{
done=false;
for(i=1; i<=n; ++i) inq[i]=false;
for(i=1; i<=n; ++i) if(!dmin[i] && dfs(i)) {done=true; ++nr;}
}while(done);
return nr;
}
bool dfs(int node){
if(inq[node]) return false;
inq[node]=true;
for(auto next:graph[node]) if(!last[next]){
last[next]=node;
dmin[node]=next;
return true;
}
for(auto next:graph[node]) if(dfs(last[next])){
last[next]=node;
dmin[node]=next;
return true;
}
return false;
}
bool refresh(int ind, bool ult){
for(i=1; i<=n; ++i) graph[i].clear();
for(i=1; i<=ind; ++i) {
if(!ult)graph[dlist[i].second.first].push_back(dlist[i].second.second);
else{
addedge(s, dlist[i].second.first, 0);
addedge(dlist[i].second.second, d, 0);
addedge(dlist[i].second.first, dlist[i].second.second, dlist[i].first);
}
}
if(!ult) return CM()==n;
return true;
}
void addedge(int i, int j, double c){
graph[i].push_back(j);
graph[j].push_back(i);
cost[i][j]=c;
cost[j][i]=-c;
flow[i][j]=1;
return;
}