Pagini recente » Cod sursa (job #2313414) | Cod sursa (job #40970) | Cod sursa (job #1551005) | Cod sursa (job #2144930) | Cod sursa (job #1223664)
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <fstream>
#include <cmath>
#include <cstring>
#define pe pair<double, double>
#define mp make_pair
#define fi first
#define se second
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
const int MAX_N = 410;
const double INF = 200000000.0;
vector<pe> ad, sl;
int n;
double MAX_E;
vector<int> A[2 * MAX_N];
vector<int> B[MAX_N];
int S, D;
int c[2 * MAX_N][2 * MAX_N];
int f[2 * MAX_N][2 * MAX_N];
double cost[2 * MAX_N][2 * MAX_N];
double dist(pe a, pe b) {
return sqrt((a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se));
}
void graf() {
S = 0;
D = 2 * n + 1;
for(int i = 1; i <= n; i++) {
A[S].push_back(i);
A[i].push_back(S);
c[S][i] = 1;
}
for(int i = n + 1; i <= 2 * n; i++) {
A[i].push_back(D);
A[D].push_back(i);
c[i][D] = 1;
}
for(int i = 1; i <= n; i++) {
for(int j = n + 1; j <= 2 * n; j++) {
B[i].push_back(j - n);
A[i].push_back(j);
A[j].push_back(i);
c[i][j] = 1;
cost[i][j] = dist(sl[i - 1], ad[j - n - 1]);
cost[j][i] = -cost[i][j];
}
}
}
int l[MAX_N];
int r[MAX_N];
bool viz[MAX_N];
bool pairup(int nod) {
if(viz[nod]) {
return false;
}
viz[nod] = true;
for(auto it : B[nod]) {
if(cost[nod][it + n] > MAX_E) {
continue;
}
if(!r[it]) {
l[nod] = it;
r[it] = nod;
return true;
}
}
for(auto it : B[nod]) {
if(cost[nod][it + n] > MAX_E) {
continue;
}
if(pairup(r[it])) {
l[nod] = it;
r[it] = nod;
return true;
}
}
return false;
}
int cuplaj(double e) {
MAX_E = e;
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
bool change = true;
while(change) {
change = false;
memset(viz, 0, sizeof(viz));
for(int i = 1; i <= n; i++) {
if(!l[i] && pairup(i)) {
change = true;
}
}
}
int sz = 0;
for(int i = 1; i <= n; i++) {
if(l[i]) {
sz++;
}
}
return sz;
}
double search(double st, double dr) {
double ans = 0;
for(int i = 1; i <= 60; i++) {
double mij = (st + dr) / 2.0;
if(cuplaj(mij) == n) {
ans = mij;
dr = mij;
}
else {
st = mij;
}
}
return ans;
}
bool inq[MAX_N * 2];
double d[MAX_N * 2];
int dad[MAX_N * 2];
double bellman() {
for(int i = 1; i <= D; i++) {
d[i] = INF;
dad[i] = 0;
inq[i] = 0;
}
queue<int> Q;
Q.push(S);
inq[S] = true;
d[S] = 0;
while(!Q.empty()) {
int nod = Q.front();
Q.pop();
inq[nod] = false;
if(nod == D) {
continue;
}
for(auto it : A[nod]) {
if(cost[nod][it] <= MAX_E && f[nod][it] < c[nod][it]) {
if(d[nod] + cost[nod][it] < d[it]) {
d[it] = d[nod] + cost[nod][it];
dad[it] = nod;
if(!inq[it]) {
Q.push(it);
inq[it] = true;
}
}
}
}
}
return d[D];
}
double maxflow() {
int fl = 0;
double cost = 0;
while(bellman() < INF) {
int p = INF;
for(int nod = D; nod != S; nod = dad[nod]) {
p = min(p, c[dad[nod]][nod] - f[dad[nod]][nod]);
}
for(int nod = D; nod != S; nod = dad[nod]) {
f[dad[nod]][nod] += p;
f[nod][dad[nod]] -= p;
}
fl += p;
cost += (double)d[D] * p;
}
return cost;
}
int main() {
fin >> n;
for(int i = 1; i <= n; i++) {
double a, b;
fin >> a >> b;
sl.push_back(mp(a, b));
}
for(int i = 1; i <= n; i++) {
double a, b;
fin >> a >> b;
ad.push_back(mp(a, b));
}
graf();
MAX_E = search(0.0, 5000.0);
fout << fixed << setprecision(13);
fout << MAX_E << ' ' << maxflow();
return 0;
}