Pagini recente » Cod sursa (job #2692391) | Cod sursa (job #247743) | Cod sursa (job #2360413) | Cod sursa (job #2301736) | Cod sursa (job #328749)
Cod sursa(job #328749)
#include <stdio.h>
#include <math.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX_N 1024
#define inf 2000000000
#define pb push_back
int n, t, improve, nr, fin;
int C[MAX_N][MAX_N], F[MAX_N][MAX_N];
int tata[MAX_N], use[MAX_N], Q[MAX_N * MAX_N];
double dist[MAX_N], sol, ValMin, SumMin;
vector <int> G[MAX_N];
double cost[MAX_N][MAX_N], d[MAX_N][MAX_N], v[MAX_N * MAX_N];
struct punct {
double x;
double y;
} S[MAX_N], A[MAX_N];
inline double distanta(punct P, punct Q) {
return sqrt((P.x - Q.x) * (P.x - Q.x) + (P.y - Q.y) * (P.y - Q.y));
}
void get_dist() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
d[i][j] = distanta(S[i], A[j]);
v[++t] = d[i][j];
}
sort(v + 1, v + t + 1);
}
void cit() {
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
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);
fin = 2 * n + 2;
//calculez distanta intre fiecare soldat si fiecare adapost
get_dist();
}
void get_graph(double x) {
for (int i = 1; i <= 2 * n + 2; i++)
G[i].clear();
memset(C, 0, sizeof(C));
memset(F, 0, sizeof(F));
memset(cost, 0, sizeof(cost));
for (int i = 1; i <= n; i++) {
C[1][i + 1] = C[n + i + 1][fin] = 1;
G[1].pb(i + 1); G[i + 1].pb(1);
G[n + i + 1].pb(fin); G[fin].pb(n + i + 1);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (d[i][j] <= x) {
C[i + 1][n + j + 1] = 1;
cost[i + 1][n + j + 1] = d[i][j];
cost[n + j + 1][i + 1] = -d[i][j];
G[i + 1].pb(n + j + 1);
G[n + j + 1].pb(i + 1);
}
}
void bellman_ford() {
memset(use, 0, sizeof(use));
memset(tata, -1, sizeof(tata));
for (int i = 1; i <= fin; i++)
dist[i] = inf;
dist[1] = 0;
int st = 0, dr = 1;
Q[1] = 1; use[1] = 1;
while (st < dr) {
st++;
int len = G[Q[st]].size();
for (int i = 0; i < len; i++)
if (C[Q[st]][G[Q[st]][i]] - F[Q[st]][G[Q[st]][i]] > 0 && dist[G[Q[st]][i]] > dist[Q[st]] + cost[Q[st]][G[Q[st]][i]]) {
tata[G[Q[st]][i]] = Q[st];
dist[G[Q[st]][i]] = dist[Q[st]] + cost[Q[st]][G[Q[st]][i]];
if (use[G[Q[st]][i]] == 0 && dist[fin] == inf) {
use[G[Q[st]][i]] = 1;
Q[++dr] = G[Q[st]][i];
}
}
use[Q[st]] = 0;
}
if (dist[fin] < inf) {
improve = 1;
int flux = inf;
for (int i = fin; i != 1; i = tata[i])
flux = min(flux, C[tata[i]][i] - F[tata[i]][i]);
for (int i = fin; i != 1; i = tata[i]) {
F[tata[i]][i] += flux;
F[i][tata[i]] -= flux;
}
nr++;
sol += flux * dist[fin];
}
}
void solve() {
int st = 0, dr = t + 1, mid = 0;
ValMin = SumMin = inf;
while (st + 1 < dr) {
mid = (st + dr) / 2;
get_graph(v[mid]);
sol = 0;
improve = 1; nr = 0;
while (improve) {
improve = 0;
bellman_ford();
}
if (nr == n) {
if (v[mid] < ValMin) {
ValMin = v[mid];
SumMin = sol;
}
dr = mid;
}
else st = mid;
}
printf("%lf %lf\n", ValMin, SumMin);
}
int main() {
cit();
solve();
return 0;
}