Pagini recente » Cod sursa (job #777687) | Cod sursa (job #701789) | Cod sursa (job #309586) | Cod sursa (job #2161923) | Cod sursa (job #3236488)
#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-9;
int N;
double x1[MAXN], y1_[MAXN], x2[MAXN], y2_[MAXN];
double dist[MAXN][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]));
}
pair<vector<int>, double> hungarian(vector<vector<double>>& cost) {
int n = cost.size(), m = cost[0].size();
vector<double> u(n+1), v(m+1), minv(m+1);
vector<int> py(m+1), way(m+1);
vector<bool> used(m+1);
for (int i = 1; i <= n; ++i) {
py[0] = i;
int j0 = 0;
fill(minv.begin(), minv.end(), INF);
fill(used.begin(), used.end(), false);
do {
used[j0] = true;
int i0 = py[j0], j1;
double delta = INF;
for (int j = 1; j <= m; ++j)
if (!used[j]) {
double cur = cost[i0-1][j-1] - u[i0] - v[j];
if (cur < minv[j]) {
minv[j] = cur;
way[j] = j0;
}
if (minv[j] < delta) {
delta = minv[j];
j1 = j;
}
}
for (int j = 0; j <= m; ++j)
if (used[j]) {
u[py[j]] += delta;
v[j] -= delta;
} else
minv[j] -= delta;
j0 = j1;
} while (py[j0] != 0);
do {
int j1 = way[j0];
py[j0] = py[j1];
j0 = j1;
} while (j0);
}
vector<int> matching(n);
for (int j = 1; j <= m; ++j)
matching[py[j]-1] = j-1;
return {matching, v[0]};
}
pair<double, double> solve() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dist[i][j] = distance(i, j);
}
}
double left = 0, right = 1500;
vector<int> best_matching;
while (right - left > EPS) {
double mid = (left + right) / 2;
vector<vector<double>> cost(N, vector<double>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cost[i][j] = (dist[i][j] <= mid) ? dist[i][j] : INF;
}
}
auto [matching, _] = hungarian(cost);
bool possible = true;
for (int i = 0; i < N; i++) {
if (dist[i][matching[i]] > mid) {
possible = false;
break;
}
}
if (possible) {
right = mid;
best_matching = matching;
} else {
left = mid;
}
}
double max_dist = right;
double sum_dist = 0;
for (int i = 0; i < N; i++) {
sum_dist += dist[i][best_matching[i]];
}
return {max_dist, sum_dist};
}
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];
auto [max_dist, sum_dist] = solve();
fout << fixed << setprecision(5) << max_dist << " " << sum_dist << endl;
return 0;
}