Pagini recente » Cod sursa (job #2182134) | Cod sursa (job #3130266) | Atasamentele paginii Clasament oji_2020_official | Cod sursa (job #2600881) | Cod sursa (job #977993)
Cod sursa(job #977993)
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
ifstream fin ("adapost.in");
ofstream fout ("adapost.out");
const double oo = 2e9, er = 1e-4;
const int N = 810, d = 805;
#define xx first
#define yy second
typedef pair <double, double> coord;
int C[N][N], n, t[N], cuplaj, A[N], B[N];
double cost[N][N], cst, dmin = oo, v[N*N/4], c[N];
coord memleft[N], memright[N];
queue <int> Q;
bool q[N], viz[N];
vector <int> g[N];
bool match(int x) {
if (viz[x])
return 0;
viz[x] = 1;
for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
if (!B[*it]) {
B[*it] = x;
A[x] = *it;
cuplaj++;
return 1;
}
for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
if (B[*it] != x && match(B[*it])) {
B[*it] = x;
A[x] = *it;
return 1;
}
return 0;
}
bool go(double x) {
for (int i = 1; i <= n; ++i)
vector <int> ().swap(g[i]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
if (cost[i][n+j] <= x + er)
g[i].push_back(j);
}
for (int i = 1; i <= n; ++i)
viz[i] = 0, A[i] = B[i] = 0;
cuplaj = 0;
bool ok = 1;
while (ok) {
ok = 0;
for (int i = 1; i <= n; ++i)
viz[i] = 0;
for (int i = 1; i <= n; ++i)
if (!A[i])
ok |= match(i);
}
return (cuplaj == n);
}
bool bellmanford() {
Q.push(0);
for (int i = 1; i <= n * 2; ++i)
c[i] = oo;
c[d] = oo;
while (Q.size()) {
int x = Q.front(); Q.pop();
q[x] = 0;
for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it) {
if (C[x][*it]) {
double NEW = c[x] + cost[x][*it];
if (NEW < c[*it] + er) {
c[*it] = NEW;
t[*it] = x;
if (!q[*it]) {
q[*it] = 1;
Q.push(*it);
}
}
}
}
}
return (c[d] != oo);
}
int main() {
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> memleft[i].xx >> memleft[i].yy;
for (int i = 1; i <= n; ++i)
fin >> memright[i].xx >> memright[i].yy;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
double now = sqrt ((memleft[i].xx - memright[j].xx) * (memleft[i].xx - memright[j].xx) + (memleft[i].yy - memright[j].yy) * (memleft[i].yy - memright[j].yy));
cost[i][n+j] = now;
cost[n+j][i] = -now;
v[(i - 1) * n + j - 1] = now;
}
sort (v, v + n * n);
int lo = 0, hi = n * n;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (go(v[mid])) {
dmin = min (dmin, v[mid]);
hi = mid;
}
else
lo = mid + 1;
}
for (int i = 1; i <= n; ++i)
vector <int> ().swap(g[i]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
if (cost[i][n+j] <= dmin + er) {
g[i].push_back(n + j); g[n + j].push_back(i);
C[i][n + j] = 1;
}
}
for (int i = 1; i <= n; ++i) {
g[0].push_back(i);
C[0][i] = 1;
g[n+i].push_back(d);
C[n+i][d] = 1;
}
while (bellmanford()) {
cst += c[d];
for (int x = d; x; x = t[x])
C[t[x]][x]--, C[x][t[x]]++;
}
fout << fixed << setprecision(5) << dmin << " " << cst;
fout.close();
}