Pagini recente » Cod sursa (job #292611) | Cod sursa (job #2717929) | Cod sursa (job #57649) | Cod sursa (job #2517356) | Cod sursa (job #612649)
Cod sursa(job #612649)
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const double eps = 0.00001;
const int INF = 2000000000;
// variabile cautb + cuplaj
const int N = 405;
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 < (int)v.size() && cuplaj(v[i + pas]) < n)
i += pas;
return i + 1;
}
// variabile flux maxim de cost minim
const int NN = 2 * N;
int S, D, dad[NN], cap[NN][NN], flux[NN][NN];
double cm, dis[NN], cost[NN][NN];
bool inq[NN];
vector <int> M[NN];
struct comp {
bool operator() (const int &a, const int &b) {
return dist[a] > dist[b];
}
};
priority_queue <int, vector<int>, comp> Q;
// formez graful ce contine toate muchiile cu cost < val si adaug o sursa si o destinatie virtuala
void init_flux(double val) {
S = 0;
for (int i = 1; i <= n; ++ i) {
M[S].push_back(i);
M[i].push_back(S);
cap[S][i] = 1;
}
D = 2 * n + 1;
for (int j = 1; j <= n; ++ j) {
M[D].push_back(n + j);
M[n + j].push_back(D);
cap[n + j][D] = 1;
}
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) {
cost[i][n + j] = dist(xs[i], ys[i], xa[j], ya[j]);
cap[i][n + j] = 1;
cost[n + j][i] = - cost[i][n + j];
M[i].push_back(n + j);
M[n + j].push_back(i);
}
}
void reset_BF() {
for (int i = S; i <= D; ++ i) {
dad[i] = - 1;
dis[i] = INF;
inq[i] = 0;
}
}
bool BF() {
int nc;
reset_BF();
Q.push(S);
inq[S] = 1;
dis[S] = 0;
while (!Q.empty()) {
nc = Q.top();
inq[nc] = 0;
Q.pop();
for (int i = 0; i < (int)M[nc].size(); ++ i)
if (flux[nc][M[nc][i]] < cap[nc][M[nc][i]] && dis[nc] + cost[nc][M[nc][i]] < dis[M[nc][i]]) {
dis[M[nc][i]] = dis[nc] + cost[nc][M[nc][i]];
dad[M[nc][i]] = nc;
if (inq[M[nc][i]] == 0) {
Q.push(M[nc][i]);
inq[M[nc][i]] = 1;
}
}
}
return (dad[D] != - 1);
}
inline int min(int x, int y) {
return x < y ? x : y;
}
// calculez fluxul maxim ce poate fi transmis pe un drum
inline void compute_flux(int &fc) {
for (int i = D; i != S; i = dad[i])
fc = min(cap[dad[i]][i] - flux[dad[i]][i], fc);
}
inline void propaga_flux(int fc) {
for (int i = D; i != S; i = dad[i]) {
flux[dad[i]][i] += fc;
flux[i][dad[i]] -= fc;
}
}
inline void baga_flux() {
int fc;
fc = INF;
compute_flux(fc);
cm += fc * dis[D];
propaga_flux(fc);
}
void fmcm() {
while (BF())
baga_flux();
}
int main() {
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
read();
init();
double rez = v[cautb()];
printf("%.6lf ", rez);
init_flux(rez);
fmcm();
printf("%.6lf\n", cm);
return 0;
}