Pagini recente » Cod sursa (job #2861810) | Cod sursa (job #2812100) | Cod sursa (job #3249961) | Cod sursa (job #579383) | Cod sursa (job #1676401)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 500;
const int NIL = -1;
const double EPS = 1e-6;
const int INF = 0x3F3F3F3F;
const int MAX_EDGES = 2 * MAX_N + 2 * MAX_N * MAX_N;
struct Point {
double x, y;
};
struct Edge {
int v;
double cost;
int cap;
int next;
};
/* retea reziduala */
Edge G[MAX_EDGES];
int head[2 * MAX_N];
int ptr;
/* cuplaj */
bool used[MAX_N];
int L[MAX_N], R[MAX_N];
/* flux maxim de cost minim */
double D[2 * MAX_N];
int dad[2 * MAX_N];
int pointer[2 * MAX_N];
bool inQueue[2 * MAX_N];
int Q[1 << 18];
bool bellmanFord(int sink) {
int b = 0, e = 1;
Q[0] = 0;
for (int i = 1; i <= sink; ++ i) {
D[i] = static_cast <double> (INF);
}
while (b != e) {
int u = Q[(b++) & 262143];
inQueue[u] = 0;
for (int i = head[u]; i != NIL; i = G[i].next) {
int v = G[i].v;
if (G[i].cap && D[v] > D[u] + G[i].cost) {
D[v] = D[u] + G[i].cost;
dad[v] = u;
pointer[v] = i;
if (!inQueue[v]) {
inQueue[v] = 1;
Q[(e++) & 262143] = v;
}
}
}
}
return D[sink] != static_cast <double> (INF);
}
double FMCM(const int source, const int sink) {
double cost = .0;
while (bellmanFord(sink)) {
cost += D[sink];
int minFlow = INF;
for (int i = sink; i != source; i = dad[i]) {
minFlow = min(minFlow, G[pointer[i]].cap);
}
for (int i = sink; i != source; i = dad[i]) {
G[pointer[i]].cap -= minFlow;
G[pointer[i] ^ 1].cap += minFlow;
}
}
return cost;
}
bool pairUp(int u) {
if (used[u]) {
return false;
}
used[u] = true;
int i = head[u];
while (i != NIL && R[G[i].v] != NIL) {
i = G[i].next;
}
if (i == NIL) {
i = head[u];
while (i != NIL && !pairUp(R[G[i].v])) {
i = G[i].next;
}
}
if (i != NIL) {
L[u] = G[i].v;
R[G[i].v] = u;
return true;
} else {
return false;
}
}
bool matching(int n) {
bool pushed;
memset(L + 1, NIL, 4 * n);
memset(R + 1, NIL, 4 * n);
do {
memset(used + 1, 0, n);
pushed = false;
for (int i = 1; i <= n; ++ i) {
if (L[i] == NIL) {
pushed |= pairUp(i);
}
}
} while (pushed);
int matched = 1;
while (matched <= n && L[matched] != NIL) {
++ matched;
}
return matched == n + 1;
}
double distance(const Point A, const Point B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
Point soldier[MAX_N];
Point shelter[MAX_N];
double dist[MAX_N][MAX_N];
void addEdge(int u, int v, int cap, double delta) {
assert(ptr < MAX_EDGES);
G[ptr].v = v;
G[ptr].cap = cap;
G[ptr].cost = delta;
G[ptr].next = head[u];
head[u] = ptr++;
}
int main() {
ifstream fin("adapost.in");
ofstream fout("adapost.out");
fin.tie(0);
ios_base::sync_with_stdio(false);
int n; fin >> n;
for (int i = 1; i <= n; ++ i) {
fin >> soldier[i].x >> soldier[i].y;
}
for (int i = 1; i <= n; ++ i) {
fin >> shelter[i].x >> shelter[i].y;
}
double b = static_cast <double> (1 << 12), e = .0;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
dist[i][j] = distance(soldier[i], shelter[j]);
if (dist[i][j] > e) {
e = dist[i][j];
}
if (dist[i][j] < b) {
b = dist[i][j];
}
}
}
while (e - b > EPS) {
double mid = (b + e) * .5;
memset(head + 1, NIL, 4 * n);
ptr = 0;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
if (mid - dist[i][j] >= EPS) {
addEdge(i, j, 0, 0);
}
}
}
if (matching(n)) {
e = mid;
} else {
b = mid;
}
}
fout << fixed << setprecision(5);
fout << e << ' ';
ptr = 0;
memset(head, NIL, 8 * (n + 1));
for (int i = 1; i <= n; ++ i) {
addEdge(0, i, 1, 0);
addEdge(i, 0, 0, 0);
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
if (e - dist[i][j] >= EPS) {
addEdge(i, n + j, 1, dist[i][j]);
addEdge(n + j, i, 0, -1.0 * dist[i][j]);
}
}
}
for (int i = 1; i <= n; ++ i) {
addEdge(n + i, n + n + 1, 1, 0);
addEdge(n + n + 1, n + i, 0, 0);
}
fout << FMCM(0, n + n + 1) << '\n';
return 0;
}