Pagini recente » Dumitrache Teodorescu Vîjială | Cod sursa (job #2752389) | Cod sursa (job #484856) | Cod sursa (job #285963) | Cod sursa (job #329713)
Cod sursa(job #329713)
#include <cstdio>
#include <math.h>
#include <vector>
#include <algorithm>
#define maxn 410
#define inf 2000000000
using namespace std;
struct punct {
double x, y;
};
int n, i, j, src, dst, ok;
punct v[2 * maxn];
int dist[2 * maxn][2 * maxn];
int dmax, cmin, cst, flow, rez;
int f[2 * maxn][2 * maxn], c[2 * maxn][2 * maxn];
int ct[2 * maxn], up[2 * maxn], viz[2 * maxn];
int q[maxn * maxn], sir[maxn * maxn], nr;
vector <int> g[2 * maxn];
inline double distanta(punct a, punct b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void init() {
// memset(up, -1, sizeof(up));
memset(viz, 0, sizeof(viz));
for (i = 0; i <= 2 * n + 1; i++)
ct[i] = inf;
}
inline int min(int a, int b) {
if (a < b)
return a;
return b;
}
int bford() {
int p, u;
int nod, fiu, i;
int unit;
p = u = 1;
q[1] = 0; viz[0] = 1; ct[0] = 0;
while (p <= u) {
nod = q[p];
int sz = g[nod].size();
for (i = 0; i < sz; i++) {
fiu = g[nod][i];
if (c[nod][fiu] - f[nod][fiu] > 0 && ct[fiu] > ct[nod] + dist[nod][fiu]) {
ct[fiu] = ct[nod] + dist[nod][fiu];
up[fiu] = nod;
if (viz[fiu] == 0) {
viz[fiu] = 1;
u++;
q[u] = fiu;
}
}
}
p++;
}
if (ct[dst] != inf) {
ok = 1;
unit = inf;
for (nod = dst; nod != src; nod = up[nod])
unit = min(unit, c[up[nod]][nod] - f[up[nod]][nod]);
for (nod = dst; nod != src; nod = up[nod]) {
f[up[nod]][nod] += unit;
f[nod][up[nod]] -= unit;
}
flow += unit;
return unit * ct[dst];
}
return 0;
}
bool solve(int d, int &cst) {
//construiesc grafu si fac flux
//toate muchiile existente o sa aiba capacitate 1
for (i = 0; i <= 2 * n + 1; i++)
g[i].clear();
src = 0;
dst = 2 * n + 1;
for (i = 1; i <= n; i++) {
f[src][i] = f[i][src] = 0;
c[i][src] = 0;
g[src].push_back(i);
g[i].push_back(src);
dist[src][i] = 0;
c[src][i] = 1;
}
for (i = n + 1; i <= 2 * n; i++) {
f[i][dst] = f[dst][i] = 0;
c[dst][i] = 0;
g[i].push_back(dst);
g[dst].push_back(i);
c[i][dst] = 1;
dist[i][dst] = 0;
}
for (i = 1; i <= n; i++)
for (j = n + 1; j <= 2 * n; j++)
if (dist[i][j] <= d) {
f[i][j] = f[j][i] = 0;
c[j][i] = 0;
g[i].push_back(j);
g[j].push_back(i);
dist[j][i] = -dist[i][j];
c[i][j] = 1;
}
ok = 1; rez = 0;
flow = 0;
while (ok) {
ok = 0;
init();
rez += bford();
}
if (flow == n) {
cst = rez;
return true;
}
return false;
}
void bsearch(int left, int right) {
int m;
while (left <= right) {
m = (left + right) / 2;
// fprintf(stderr, "%d\n", m);
if (solve(sir[m], cst)) {
if (sir[m] < dmax) {
dmax = sir[m];
cmin = cst;
}
right = m - 1;
}
else
left = m + 1;
}
}
int main() {
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
scanf("%d", &n);
for (i = 1; i <= 2 * n; i++)
scanf("%lf%lf", &v[i].x, &v[i].y);
for (i = 1; i <= n; i++)
for (j = n + 1; j <= 2 * n; j++) {
dist[i][j] = (int) (10000 * distanta(v[i], v[j]));
nr++;
sir[nr] = dist[i][j];
}
sort(sir + 1, sir + nr + 1);
dmax = inf;
bsearch(1, nr);
printf("%d.", dmax / 10000);
int x = dmax % 10000;
int y = 1;
if (x == 0)
printf("000");
else
while (x * y < 1000) {
y *= 10;
printf("0");
}
printf("%d ", x);
dmax = cmin;
y = 1;
printf("%d.", dmax / 10000);
x = dmax % 10000;
if (x == 0)
printf("000");
else
while (x * y < 1000) {
y *= 10;
printf("0");
}
printf("%d\n", x);
return 0;
}