Pagini recente » Cod sursa (job #1812754) | Cod sursa (job #1330058) | Cod sursa (job #2556301) | Cod sursa (job #2024218) | Cod sursa (job #1397387)
#include <stdio.h>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <string.h>
#include <algorithm>
#define MAXN 420
#define INF 1e5
#define EPS 1e-6
#define x first
#define y second
using namespace std;
const int off = 405, start = 0, fin = 402;
int n, cap[2 * MAXN][2 * MAXN], fx[2 * MAXN][2 * MAXN], bk[2 * MAXN];
double totcst;
vector<double> dst;
pair<double, double> pct[MAXN], ad[MAXN];
vector< pair<int, double> > G[2 * MAXN];
double dstb[2 * MAXN];
inline double euclidDist(pair<double, double> a, pair<double, double> b){
double dx = a.x - b.x, dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
bool Bellman_Ford(double mx_c){
int i, a;
bool uzq[2 * MAXN];
queue<int> q;
for(i = 0; i <= n + off; i++){
dstb[i] = INF;
bk[i] = -1;
uzq[i] = 0;
}
dstb[start] = 0;
q.push(start); uzq[start] = 1;
while(!q.empty()){
a = q.front(); q.pop();
uzq[a] = 0;
for(auto b: G[a]){
if(fabs(b.second) < mx_c + EPS && fx[a][b.first] < cap[a][b.first] && dstb[a] + b.second < dstb[b.first]){
dstb[b.first] = dstb[a] + b.second;
bk[b.first] = a;
if(!uzq[b.first]){ uzq[b.first] = 1; q.push(b.first); }
}
}
}
return dstb[fin] < INF;
}
bool works(double mx_c){
int totfx = 0, a;
totcst = 0;
memset(fx, 0, sizeof(fx));
while(Bellman_Ford(mx_c)){
totfx++;
totcst += dstb[fin];
a = fin;
while(bk[a] != -1){
fx[bk[a]][a]++;
fx[a][bk[a]]--;
a = bk[a];
}
}
return (totfx == n);
}
int main(){
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
int i, j;
scanf("%d", &n);
for(i = 1; i <= n; i++)
scanf("%lf %lf", &pct[i].x, &pct[i].y);
for(i = 1; i <= n; i++)
scanf("%lf %lf", &ad[i].x, &ad[i].y);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++){
dst.push_back(euclidDist(pct[i], ad[j]));
G[i].push_back(make_pair(j + off, dst.back()));
G[j + off].push_back(make_pair(i, -dst.back()));
cap[i][j + off] = 1;
}
sort(dst.begin(), dst.end());
for(i = 1; i <= n; i++){
cap[start][i] = cap[i + off][fin] = 1;
G[start].push_back(make_pair(i, 0));
G[i + off].push_back(make_pair(fin, 0));
}
int l = 0, r = dst.size() - 1, mid;
while(l < r){
mid = (l + r) >> 1;
if(works(dst[mid])) r = mid - 1;
else l = mid + 1;
}
while(r < 0 || !works(dst[r])) r++;
printf("%.7lf %.7lf\n", dst[r], totcst);
return 0;
}