Pagini recente » Cod sursa (job #3282521) | Cod sursa (job #3232456) | Cod sursa (job #3183864) | Cod sursa (job #3282887) | Cod sursa (job #3236483)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#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];
vector<int> g[MAXN];
int match[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]));
}
bool bfs(double threshold) {
static int prev[MAXN];
queue<int> q;
for (int i = 0; i < N; i++) {
if (match[i] == -1) {
q.push(i);
prev[i] = -1;
} else {
prev[i] = -2;
}
}
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : g[v]) {
if (dist[v][u] > threshold) continue;
if (match[u] == -1) {
while (v != -1) {
int pv = match[v];
match[v] = u;
match[u] = v;
v = pv;
u = prev[v];
}
return true;
}
if (prev[match[u]] == -2) {
prev[match[u]] = v;
q.push(match[u]);
}
}
}
return false;
}
pair<double, double> solve() {
vector<double> all_distances;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dist[i][j] = distance(i, j);
all_distances.push_back(dist[i][j]);
}
}
sort(all_distances.begin(), all_distances.end());
double left = 0, right = all_distances.back();
while (right - left > EPS) {
double mid = (left + right) / 2;
for (int i = 0; i < N; i++) {
g[i].clear();
for (int j = 0; j < N; j++) {
if (dist[i][j] <= mid) {
g[i].push_back(j);
}
}
}
fill(match, match + N, -1);
int matches = 0;
while (bfs(mid)) {
matches++;
}
if (matches == N) {
right = mid;
} else {
left = mid;
}
}
double max_dist = right;
// Calculate minimum sum
double sum_dist = 0;
for (int i = 0; i < N; i++) {
sum_dist += dist[i][match[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;
}