Pagini recente » Cod sursa (job #2259056) | Cod sursa (job #2550261) | Monitorul de evaluare | Cod sursa (job #1644247) | Cod sursa (job #1666498)
#include <bits/stdc++.h>
using namespace std;
ifstream in("adapost.in");
ofstream out("adapost.out");
const int N = 405;
const int INF = 1e9;
const double eps = 1e-7;
pair<double, double> sld[N], shl[N];
vector<double> dlist;
double cost[2*N][2*N], dist[2*N], cbest, cmax, csum, dbest;
bool inque[2*N], cap[2*N][2*N], vis[N];
char flow[2*N][2*N];
int f[2*N], n, fsum, l[N], r[N];
queue<int> q;
inline int cmp(double a, double b) {
if (a-b < -eps) return -1;
if (a-b > eps) return 1;
return 0;
}
bool pair_up(int x) {
if(vis[x]) return 0;
vis[x] = 1;
for(int i = 1; i <= n; i++) {
if(cmp(cost[x][n+i], cmax) <= 0 && !r[i]) {
r[i] = x;
l[x] = i;
return 1;
}
}
for(int i = 1; i <= n; i++) {
if(cmp(cost[x][n+i], cmax) <= 0 && pair_up(r[i])) {
r[i] = x;
l[x] = i;
return 1;
}
}
return 0;
}
bool max_match() {
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
bool done;
do {
done = 1;
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++) {
if(!l[i] && pair_up(i)) {
done = 0;
}
}
} while(!done);
for(int i = 1; i <= n; i++) {
if(!l[i]) return 0;
}
return 1;
}
bool bellman() {
int i, j;
memset(inque, 0, sizeof(inque));
memset(f, 0, sizeof(f));
for(i = 1; i <= 2*n+1; i++) dist[i] = INF;
inque[0] = 1;
dist[0] = 0;
q.push(0);
while(!q.empty()) {
i = q.front();
inque[i] = 0;
q.pop();
for(j = 0; j <= 2*n+1; j++) {
if(flow[i][j] < cap[i][j] && cmp(cost[i][j], cmax) <= 0) {
if(cmp(dist[j], dist[i] + cost[i][j]) > 0) {
dist[j] = dist[i] + cost[i][j];
f[j] = i;
if(!inque[j]) {
inque[j] = 1;
q.push(j);
}
}
}
}
}
return f[2*n+1];
}
void get_flow() {
memset(flow, 0, sizeof(flow[0][0])*N*N);
csum = fsum = 0;
while(bellman()) {
for(int i = 2*n+1; i != 0; i = f[i]) {
flow[f[i]][i]++;
flow[i][f[i]]--;
csum += cost[f[i]][i];
}
fsum++;
}
}
int bins() {
int lo = 0, hi = n*n, med;
while(lo <= hi) {
med = (lo+hi)>>1;
cmax = dlist[med];
if(max_match()) hi = med-1;
else lo = med+1;
}
return hi+1;
}
int main() {
int i, j;
double x, y, d;
in >> n;
for(i = 1; i <= n; i++) {
in >> x >> y;
sld[i] = make_pair(x, y);
}
for(i = 1; i <= n; i++) {
in >> x >> y;
shl[i] = make_pair(x, y);
}
for(i = 1; i <= n; i++) {
cap[0][i] = 1;
cap[i+n][2*n+1] = 1;
for(j = 1; j <= n; j++) {
x = sld[i].first - shl[j].first;
y = sld[i].second - shl[j].second;
d = sqrt(x*x + y*y);
dlist.push_back(d);
cost[i][j+n] = d;
cost[j+n][i] = -d;
cap[i][j+n] = 1;
}
}
sort(dlist.begin(), dlist.end());
cmax = dlist[bins()];
//get_flow();
out << fixed << setprecision(10) << cmax << ' ' << csum << '\n';
return 0;
}