Pagini recente » Cod sursa (job #464169) | Cod sursa (job #377408) | Cod sursa (job #1692422) | Cod sursa (job #3148516) | Cod sursa (job #48062)
Cod sursa(job #48062)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<double, double>point;
const int NMAX = 401;
const double eps = 1.0e-3;
point s[NMAX], ad[NMAX];
double d[NMAX][NMAX];
int cap[2 * NMAX][2 * NMAX];
vector<int>lv[2 * NMAX];
int n;
inline double sqr(double x) {
return x * x;
}
int pi[2 * NMAX], q[2 * NMAX];
int bf() {
int l, r;
q[0] = 0;
memset(pi, -1, 8 * NMAX);
pi[0] = 0;
for (l = 0, r = 1; l < r; ++l) {
vector<int>::iterator it;
// printf ("%d\n", q[l]);
for (it = lv[q[l]].begin(); it != lv[q[l]].end(); ++it) {
if (cap[q[l]][*it] && pi[*it] == -1) {
// printf ("--%d\n", *it);
q[r++] = *it;
pi[*it] = q[l];
if ((*it) == 2 * n + 1) {
return 1;
}
}
}
}
return 0;
}
void build(double lim) {
int i, j;
lv[0].clear();
lv[2 * n + 1].clear();
for (i = 1; i <= n; ++i) {
lv[i].clear();
lv[0].push_back(i);
lv[i].push_back(0);
lv[n + i].clear();
lv[n + i].push_back(2 * n + 1);
lv[2 * n + 1].push_back(n + i);
}
for (i = 1; i <= n; ++i) {
cap[0][i] = 1;
cap[i][0] = 0;
cap[n + i][2 * n + 1] = 1;
cap[2 * n + 1][n + i] = 0;
for (j = 1; j <= n; ++j) {
if (d[i][j] <= lim) {
cap[i][n + j] = 1;
lv[i].push_back(n + j);
lv[n + j].push_back(i);
} else {
cap[i][n + j] = 0;
}
cap[n + j][i] = 0;
}
}
}
int flow(double lim) {
int i, j, ret = 0;
build(lim);
//Pun muchii cu greedy
for (i = 1; i <= n; ++i) {
for (j = n + 1; j <= 2 * n; ++j) {
if (cap[i][j] && cap[j][2 * n + 1]) {
cap[0][i] = 0;
cap[i][0] = 1;
cap[i][j] = 0;
cap[j][i] = 1;
cap[j][2 * n + 1] = 0;
cap[2 * n + 1][j] = 1;
ret++;
break;
}
}
}
//Fluxul propriu-zis
while (bf()) {
int nod = 2 * n + 1;
while (nod != 0) {
// printf ("Nod = %d\n", nod);
cap[nod][pi[nod]] = 1;
cap[pi[nod]][nod] = 0;
nod = pi[nod];
}
ret++;
}
return ret >= n ? 1 : 0; //De fapt era ret == n ? 1 : 0
}
int main() {
FILE *fin = fopen ("adapost.in", "r");
FILE *fout = fopen ("adapost.out", "w");
fscanf (fin, "%d", &n);
int i, j;
for (i = 1; i <= n; ++i) {
fscanf (fin, "%lf %lf", &s[i].first, &s[i].second);
}
for (i = 1; i <= n; ++i) {
fscanf (fin, "%lf %lf", &ad[i].first, &ad[i].second);
}
vector<double>allV;
for (i = 1; i <= n; ++i) {
for (j = 1; j <= n; ++j) {
d[i][j] = sqrt(sqr(s[i].first - ad[j].first) + sqr(s[i].second - ad[j].second));
allV.push_back(d[i][j]);
}
}
sort(allV.begin(), allV.end());
int sol = allV.size() - 1, step;
for (step = 1; (step << 1) < allV.size(); step <<=1);
for (; step; step>>=1) {
if (sol - step >= 0 && flow(allV[sol - step])) {
sol -= step;
}
}
fprintf (fout, "%lf 0\n", allV[sol]);
fclose(fout);
return 0;
}