Pagini recente » Cod sursa (job #548632) | Cod sursa (job #1773096) | Cod sursa (job #3137366) | Cod sursa (job #1074047) | Cod sursa (job #566247)
Cod sursa(job #566247)
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_N 810
#define inf 1000000000
#define eps 0.000001
#define mp make_pair
int n, m, s, d, k;
int viz[MAX_N], cuplaj[MAX_N];
double dmin = inf, sol, SUM;
vector <int> G[MAX_N];
bool improve;
int C[MAX_N][MAX_N], F[MAX_N][MAX_N];
double cost[MAX_N][MAX_N];
int tata[MAX_N], h[MAX_N], pos[MAX_N];
double D[MAX_N];
struct punct {
double x, y;
} A[MAX_N], B[MAX_N];
inline double dist(int p, int q) {
return sqrt((A[p].x - B[q].x) * (A[p].x - B[q].x) + (A[p].y - B[q].y) * (A[p].y - B[q].y));
}
void get_graph(double k) {
for (int i = 1; i <= n; i++)
vector <int> ().swap(G[i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (dist(i, j) <= k + eps)
G[i].push_back(j);
}
bool cupleaza(int x) {
if (viz[x])
return false;
viz[x] = 1;
for (vector <int>::iterator it = G[x].begin(); it != G[x].end(); ++it)
if (cuplaj[*it] == 0) {
cuplaj[*it] = x;
m++;
return true;
}
for (vector <int>::iterator it = G[x].begin(); it != G[x].end(); ++it)
if (cuplaj[*it] != x && cupleaza(cuplaj[*it])) {
cuplaj[*it] = x;
return true;
}
return false;
}
void get_dmin() {
double value[MAX_N * MAX_N];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
value[(i - 1) * n + j] = dist(i, j);
sort(value + 1, value + n * n + 1);
int left = 0, right = n * n + 1, mid = 0;
while (left + 1 < right) {
mid = (left + right) / 2;
get_graph(value[mid]);
memset(cuplaj, 0, sizeof(cuplaj)); m = 0;
for (int i = 1; i <= n; i++) {
memset(viz, 0, sizeof(viz));
cupleaza(i);
}
if (m == n) {
right = mid;
dmin = min(dmin, value[mid]);
}
else
left = mid;
}
}
void build_flow_graph() {
s = 1; d = 2 * n + 2;
for (int i = 1; i <= d; i++)
vector <int> ().swap(G[i]);
for (int i = 1; i <= n; i++) {
G[s].push_back(i + 1); C[s][i + 1] = 1;
G[i + 1].push_back(s);
G[n + i + 1].push_back(d); C[n + i + 1][d] = 1;
G[d].push_back(n + i + 1);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (dist(i, j) <= dmin + eps) {
G[i + 1].push_back(n + j + 1); cost[i + 1][n + j + 1] = dist(i, j); C[i + 1][n + j + 1] = 1;
G[n + j + 1].push_back(i + 1); cost[n + j + 1][i + 1] = -dist(i, j);
}
}
void get_distance() {
for (int i = 1; i <= d; i++)
D[i] = inf;
D[s] = 0;
for (int iterations = 0; iterations < d; iterations++) {
bool update = 0;
for (int i = 1; i <= d; i++)
for (vector <int>::iterator it = G[i].begin(); it != G[i].end(); ++it)
if (C[i][*it] && D[i] + cost[i][*it] < D[*it]) {
D[*it] = D[i] + cost[i][*it];
update = true;
}
if (!update)
break;
}
SUM = D[d];
}
void update_flow_graph() {
for (int i = 1; i <= d; i++)
for (vector <int>::iterator it = G[i].begin(); it != G[i].end(); ++it)
if (D[i] != inf && D[*it] != inf)
cost[i][*it] = cost[i][*it] + D[i] - D[*it];
}
void heap_update(int x) {
//down-heap
if (x > 1 && D[h[x / 2]] > D[h[x]]) {
swap(h[x], h[x / 2]);
pos[h[x]] = x; pos[h[x / 2]] = x / 2;
x /= 2;
}
//up-heap
while ((x * 2 <= k && D[h[x * 2]] < D[h[x]]) || (x * 2 + 1 <= k && D[h[x * 2 + 1]] < D[h[x]])) {
int nxt = x * 2;
if (x * 2 + 1 <= k && D[h[x * 2 + 1]] < D[h[x * 2]])
nxt = x * 2 + 1;
swap(h[x], h[nxt]);
pos[h[x]] = x; pos[h[nxt]] = nxt;
x = nxt;
}
}
double dijkstra() {
update_flow_graph();
for (int i = 1; i <= d; i++) {
D[i] = inf;
tata[i] = viz[i] = 0;
}
D[s] = 0;
h[k = 1] = s; pos[s] = viz[s] = 1;
while (k) {
int nod = h[1];
// for (int i = 1; i <= k; i++)
// printf("%d %d %lf\n", i, h[i], D[h[i]]);
// printf("\n");
for (vector <int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it) {
if (C[nod][*it] > F[nod][*it] && D[*it] > D[nod] + cost[nod][*it]) {
D[*it] = D[nod] + cost[nod][*it];
tata[*it] = nod;
if (viz[*it] == 0) {
h[++k] = *it;
pos[*it] = k;
}
// if (*it == 10 && D[10] == 0)
// printf("***\n");
heap_update(pos[*it]);
viz[*it] = 1;
}
}
// for (int i = 1; i <= k; i++)
// printf("%d %d %lf\n", i, h[i], D[h[i]]);
// printf("\n");
int x = pos[nod];
swap(h[x], h[k]);
pos[h[x]] = x; pos[h[k]] = 0; h[k--] = 0;
heap_update(x);
}
// for (int i = 1; i <= d; i++)
// printf("%lf ", D[i]);
// printf("\n");
if (D[d] != inf) {
improve = true;
for (int i = d; i != s; i = tata[i]) {
F[tata[i]][i]++;
F[i][tata[i]]--;
}
SUM += D[d];
return SUM;
}
return 0;
}
void solve() {
get_dmin();
build_flow_graph();
get_distance();
improve = true;
while (improve) {
improve = false;
sol += dijkstra();
}
printf("%lf %lf\n", dmin, sol);
}
int main() {
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lf %lf", &A[i].x, &A[i].y);
for (int i = 1; i <= n; i++)
scanf("%lf %lf", &B[i].x, &B[i].y);
solve();
return 0;
}