Pagini recente » Cod sursa (job #1942467) | Cod sursa (job #2393951) | Cod sursa (job #617511) | Cod sursa (job #392822) | Cod sursa (job #3236481)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
const int MAXN = 405;
const double INF = 1e9;
const double EPS = 1e-6;
int N;
double x1[MAXN], y1[MAXN], x2[MAXN], y2[MAXN];
double dist[MAXN][MAXN];
double lx[MAXN], ly[MAXN], slack[MAXN];
int xy[MAXN], yx[MAXN], prev[MAXN];
bool S[MAXN], T[MAXN];
double sqr(double x) {
return x * x;
}
double distance(int i, int j) {
return sqrt(sqr(x1[i] - x2[j]) + sqr(y1[i] - y2[j]));
}
void add_to_tree(int x, int prevx) {
S[x] = true;
prev[x] = prevx;
for (int y = 0; y < N; y++)
if (lx[x] + ly[y] - dist[x][y] < slack[y] - EPS) {
slack[y] = lx[x] + ly[y] - dist[x][y];
yx[y] = x;
}
}
void update_labels() {
double delta = INF;
for (int y = 0; y < N; y++)
if (!T[y])
delta = min(delta, slack[y]);
for (int x = 0; x < N; x++)
if (S[x]) lx[x] -= delta;
for (int y = 0; y < N; y++)
if (T[y]) ly[y] += delta;
else slack[y] -= delta;
}
void augment() {
if (xy[N - 1] != -1) return;
int x, y, root;
int q[MAXN], wr = 0, rd = 0;
for (int i = 0; i < N; i++) {
S[i] = T[i] = false;
prev[i] = -1;
}
for (x = 0; x < N; x++)
if (xy[x] == -1) {
q[wr++] = root = x;
prev[x] = -2;
S[x] = true;
break;
}
for (y = 0; y < N; y++) {
slack[y] = lx[root] + ly[y] - dist[root][y];
yx[y] = root;
}
while (true) {
while (rd < wr) {
x = q[rd++];
for (y = 0; y < N; y++)
if (!T[y] && abs(lx[x] + ly[y] - dist[x][y]) < EPS) {
if (yx[y] == -1) {
while (y != -2) {
int ty = xy[x];
yx[y] = x;
xy[x] = y;
x = prev[x];
y = ty;
}
return;
}
T[y] = true;
q[wr++] = yx[y];
add_to_tree(yx[y], x);
}
}
update_labels();
wr = rd = 0;
for (y = 0; y < N; y++)
if (!T[y] && abs(slack[y]) < EPS) {
if (yx[y] == -1) {
x = yx[y];
while (y != -2) {
int ty = xy[x];
yx[y] = x;
xy[x] = y;
x = prev[x];
y = ty;
}
return;
} else {
T[y] = true;
if (!S[yx[y]]) {
q[wr++] = yx[y];
add_to_tree(yx[y], yx[y]);
}
}
}
}
}
double hungarian() {
for (int i = 0; i < N; i++) {
lx[i] = ly[i] = 0;
xy[i] = yx[i] = -1;
for (int j = 0; j < N; j++)
lx[i] = max(lx[i], dist[i][j]);
}
for (int i = 0; i < N; i++)
augment();
double ret = 0;
for (int i = 0; i < N; i++)
ret += dist[i][xy[i]];
return ret;
}
bool check(double mid) {
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
dist[i][j] = (distance(i, j) <= mid ? distance(i, j) : INF);
hungarian();
for (int i = 0; i < N; i++)
if (xy[i] == -1) return false;
return true;
}
int main() {
ifstream fin("adapost.in");
ofstream fout("adapost.out");
fin >> N;
for (int i = 0; i < N; i++)
fin >> x1[i] >> y1[i];
for (int i = 0; i < N; i++)
fin >> x2[i] >> y2[i];
double lo = 0, hi = 1500;
while (hi - lo > EPS) {
double mid = (lo + hi) / 2;
if (check(mid))
hi = mid;
else
lo = mid;
}
double max_dist = hi;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
dist[i][j] = distance(i, j);
double sum_dist = hungarian();
fout << fixed << setprecision(5) << max_dist << " " << sum_dist << endl;
return 0;
}