Pagini recente » Cod sursa (job #1924319) | Cod sursa (job #1049079) | Cod sursa (job #1264944) | Cod sursa (job #1593820) | Cod sursa (job #2085758)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 400;
const double INF = 1000000;
const double eps = 1.e-6;
struct Punct {
double x, y;
}s[MAX_N + 5], a[MAX_N + 5];
struct Date {
int u, v;
double d;
bool operator < (const Date& other) const {
return d - other.d < eps;
}
}aux[MAX_N * MAX_N + 5];
double distanta(Punct a, Punct b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
vector<int>E[MAX_N + 5];
vector<int>G[(2 * MAX_N + 2) + 5];
int l[MAX_N + 5], r[MAX_N + 5];
bool viz[MAX_N + 5];
bool match(int nod) {
if (viz[nod])
return false;
viz[nod] = 1;
for (auto it:E[nod]) {
if (l[it] == 0) {
r[nod] = it;
l[it] = nod;
return true;
}
}
for (auto it:E[nod]) {
if (!viz[l[it]] && match(l[it])) {
r[nod] = it;
l[it] = nod;
return true;
}
}
return false;
}
int cuplaj(int med, int n) {
for (int i = 1; i <= med; ++i)
E[aux[i].u].push_back(aux[i].v);
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
bool ok;
do {
ok = false;
memset(viz, 0, sizeof(viz));
for (int i = 1; i <= n; ++i) {
if (r[i] == 0 && match(i))
ok = true;
}
} while (ok);
int ans = 0;
for (int i = 1; i <= n; ++i)
if (r[i])
ans++;
return ans;
}
int nrv[(2 * MAX_N + 2) + 5];
bool inc[(2 * MAX_N + 2) + 5];
double dist[(2 * MAX_N + 2) + 5];
int from[(2 * MAX_N + 2) + 5];
int cr[(2 * MAX_N + 2) + 5][(2 * MAX_N + 2) + 5];
double cost[(2 * MAX_N + 2) + 5][(2 * MAX_N + 2) + 5];
double bellman(int s, int d, int n) {
for (int i = 1; i <= n; ++i) {
dist[i] = INF;
nrv[i] = 0;
inc[i] = 0;
}
inc[s] = 1;
from[s] = s;
nrv[s] = 1;
dist[s] = 0;
queue<int>q;
q.push(s);
while (!q.empty() && nrv[q.front()] < n) {
int node = q.front();
q.pop();
inc[node] = 0;
for (auto it:G[node]) {
if (cr[node][it] > 0 && dist[node] + cost[node][it] - dist[it] < eps) {
from[it] = node;
dist[it] = dist[node] + cost[node][it];
if (inc[it] == 0) {
inc[it] = 1;
q.push(it);
nrv[it]++;
}
}
}
}
return dist[d];
}
double cmcm(int s, int d, int n) {
double ans = 0, dm;
dm = bellman(s, d, n);
while (dm != INF) {
int aux = INF;
int node = d;
while (node != s) {
aux = min(aux, cr[from[node]][node]);
node = from[node];
}
node = d;
while (node != s) {
cr[from[node]][node] -= aux;
cr[node][from[node]] += aux;
node = from[node];
}
ans += dm * aux;
dm = bellman(s, d, n);
}
return ans;
}
int main() {
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%Lf%Lf", &s[i].x, &s[i].y);
for (int i = 1; i <= n; ++i)
scanf("%Lf%Lf", &a[i].x, &a[i].y);
int k = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
aux[++k] = {i, j, distanta(s[i], a[j])};
sort(aux + 1, aux + k + 1);
int st = 1, dr = k;
int last = 0;
while (st <= dr) {
int med = (st + dr) >> 1;
if (cuplaj(med, n) == n) {
last = med;
dr = med - 1;
} else {
st = med + 1;
}
}
printf("%.4f ", aux[last].d);
for (int i = 1; i <= last; ++i) {
G[aux[i].u + 1].push_back(aux[i].v + n + 1);
G[aux[i].v + n + 1].push_back(aux[i].u + 1);
cr[aux[i].u + 1][aux[i].v + n + 1] = 1;
cost[aux[i].u + 1][aux[i].v + n + 1] = aux[i].d;
cost[aux[i].v + n + 1][aux[i].u + 1] = -aux[i].d;
}
for (int i = 2; i <= n + 1; ++i) {
G[1].push_back(i + 1);
G[i + 1].push_back(1);
cr[1][i] = 1;
}
for (int i = n + 2; i <= 2 * n + 1; ++i) {
G[i].push_back(2 * n + 2);
G[2 * n + 2].push_back(i);
cr[i][2 * n + 2] = 1;
}
printf("%.4f\n", cmcm(1, 2 * n + 2, 2 * n + 2));
return 0;
}