Pagini recente » Cod sursa (job #3362079) | Cod sursa (job #3361589) | Cod sursa (job #3361591) | Cod sursa (job #3361285) | Cod sursa (job #3362072)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <stack>
#include <iomanip>
#include <queue>
// #include <bits/std++.h>
#define in fin
#define out fout
using namespace std;
const int NMAX = 400 * 2 + 5;
const double eps = 1e-5;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
struct muchie{
int x, y, pereche, c, f;
double cost;
};
struct punct{
double x, y;
};
double distanta(punct &a, punct &b){
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
vector<muchie> mch;
vector<int> g[NMAX];
int sursie, noelle;
int cuplaj[NMAX];
bool mrc[NMAX];
int n;
void add_muchie(int x, int y, int c, double cost){
int id = mch.size(), idp = id + 1;
mch.push_back({x, y, idp, c, 0, cost});
mch.push_back({y, x, id, 0, 0, -cost});
g[x].push_back(id);
g[y].push_back(idp);
}
bool pair_up(int nod, double dist){
if(mrc[nod]) return 0;
mrc[nod] = 1;
// cerr << "dist = " << dist << '\n';
for(const int &id : g[nod]){
int cop = mch[id].y;
if(mch[id].cost > dist * dist) continue;
if(-mch[id].cost > dist * dist) continue;
if(cop == sursie || cop == noelle) continue; // ei nu conteaza la cuplaj
// cerr << "cuplaj[cop] = " << cuplaj[cop] << '\n';
if(!cuplaj[cop] || pair_up(cuplaj[cop], dist)){
cuplaj[cop] = nod;
cuplaj[nod] = cop;
// cerr << "--> fac pair up" << '\n';
return 1;
}
}
return 0;
}
bool verifica_te_rog(double dist){
for(int i = 1; i <= 2 * n + 2; i++){
cuplaj[i] = 0;
}
int total = 0;
// cerr << "incep sa verific dist = " << fixed << setprecision(3) << dist << '\n';
bool ghost_bath_is_asa_peak = 1; // in special albumui burial
while(ghost_bath_is_asa_peak){ // asta e ca un while true cu conditia asta...
ghost_bath_is_asa_peak = 0;
for(int i = 1; i <= n; i++) mrc[i] = 0;
for(int i = 1; i <= n; i++){
// cerr << "i = " << i << '\n';
if(!cuplaj[i] && pair_up(i, dist)){
ghost_bath_is_asa_peak = 1;
total++;
// cerr << "adaug unu pentru i = " << i << '\n';
}
}
}
// cerr << "total = " << total << '\n';
return (total == n); // toti gasesc adapost in dist rezonabila
}
signed main(){
ios_base::sync_with_stdio(false);
in.tie(NULL);
in >> n;
punct sold[n], adp[n];
for(int i = 0; i < n; i++) in >> sold[i].x >> sold[i].y;
for(int i = 0; i < n; i++) in >> adp[i].x >> adp[i].y;
sursie = 2 * n + 1;
noelle = sursie + 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
// cout << "i = " << i << " j = " << j << " dist = " << distanta(sold[i], adp[j]) << '\n';
add_muchie(i + 1, j + n + 1, 1, distanta(sold[i], adp[j]));
}
}
double l = 0, r = 1000000.0;
double sol = 0;
for(int it = 0; it < 100; it++){
double m = (l + r) / 2.0;
if(verifica_te_rog(m)){
sol = m;
r = m - eps;
}else l = m + eps;
}
out << fixed << setprecision(4) << sol << '\n';
for(int i = 1; i <= n; i++){
add_muchie(sursie, i, 1, 0);
add_muchie(i + n, noelle, 1, 0);
}
return 0;
}