Pagini recente » Cod sursa (job #1007892) | Cod sursa (job #513008) | Cod sursa (job #2895267) | Cod sursa (job #2525696) | Cod sursa (job #1666493)
#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];
char flow[2*N][2*N];
int f[2*N], n, fsum;
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 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 getFlow() {
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 = 3, med;
while(lo <= hi) {
med = (lo+hi)>>1;
cmax = dlist[med];
getFlow();
if(fsum == n) 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());
i = bins();
cmax = dlist[i];
getFlow();
out << fixed << setprecision(10) << cmax << ' ' << csum << '\n';
return 0;
}