Pagini recente » Cod sursa (job #2114585) | Cod sursa (job #2928324) | Cod sursa (job #616702) | Cod sursa (job #612648) | Cod sursa (job #612638)
Cod sursa(job #612638)
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 405;
const double eps = 0.000001;
int n, st[N], dr[N];
double xs[N], ys[N], xa[N], ya[N];
vector <double> v;
vector <int> L[N];
bool viz[N];
void read() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
scanf("%lf%lf", &xs[i], &ys[i]);
for (int i = 1; i <= n; ++ i)
scanf("%lf%lf", &xa[i], &ya[i]);
}
// distanta dintre doua puncte
double dist(double x1, double y1, double x2, double y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
// formez vectorul cu valorile ce pot fi luate de costurile muchiilor
void init() {
v.push_back(0);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
v.push_back(dist(xs[i], ys[i], xa[j], ya[j]));
sort(v.begin(), v.end());
}
void reset_graf() {
for (int i = 1; i <= n; ++ i)
L[i].clear();
for (int i = 1; i <= n; ++ i)
st[i] = dr[i] = 0;
}
// adaug in graf doar muchiile cu costuri < val
void make_graf(double val) {
reset_graf();
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
if (dist(xs[i], ys[i], xa[j], ya[j]) <= val + eps)
L[i].push_back(j);
}
void reset(bool a[N]) {
for (int i = 1; i <= n; ++ i)
a[i] = 0;
}
bool pair_up(int nod) {
if (viz[nod])
return 0;
viz[nod] = 1;
for (int i = 0; i < (int)L[nod].size(); ++ i)
if (!dr[L[nod][i]]) {
st[nod] = L[nod][i];
dr[L[nod][i]] = nod;
return 1;
}
for (int i = 0; i < (int)L[nod].size(); ++ i)
if (pair_up(dr[L[nod][i]])) {
st[nod] = L[nod][i];
dr[L[nod][i]] = nod;
return 1;
}
return 0;
}
int cuplaj(double val) {
bool ok = 1;
int nrp = 0;
make_graf(val);
while (ok) {
ok = 0;
reset(viz);
for (int i = 1; i <= n; ++ i)
if (!st[i] && pair_up(i)) {
++ nrp;
ok = 1;
}
}
return nrp;
}
int cautb() {
int i = 0, pas = 1;
while ((pas << 1) < v.size())
pas <<= 1;
for (i = 0; pas; pas >>= 1)
if (i + pas < v.size() && cuplaj(v[i + pas]) < n)
i += pas;
return i + 1;
}
int main() {
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
read();
init();
double rez = v[cautb()];
printf("%.6lf ", rez);
printf("0\n");
return 0;
}