Pagini recente » Cod sursa (job #79764) | Cod sursa (job #781668) | Cod sursa (job #141531) | Cod sursa (job #2391531) | Cod sursa (job #1887769)
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
#define x first
#define y second
#define MAXN 802
#define EPS (1e-6)
#define INF 0x3f3f3f3f
using namespace std;
vector <int> G[MAXN];
pair <double, double> man[MAXN/2], house[MAXN/2];
double mincost, flow[MAXN][MAXN], cost[MAXN][MAXN], capacity[MAXN][MAXN], dist[MAXN];
int source, sink, n, q[MAXN*MAXN], dad[MAXN];
bool inq[MAXN];
inline double mydistance(pair <double, double> p1, pair<double, double> p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}
inline bool bellmanford(double d)
{
int node, son, i, left, right;
for(i=0; i<=2*n+1; ++i)
dist[i] = 1.0*INF;
dist[0] = 0;
left = right = 0;
q[right++] = source;
inq[source] = 1;
while(left < right) {
node = q[left++];
inq[node] = 0;
if(node == sink) continue;
for(i=0; i<G[node].size(); ++i) {
son = G[node][i];
if(cost[node][son] < d+EPS && flow[node][son] < capacity[node][son] && dist[node] + cost[node][son] < dist[son]) {
dist[son] = dist[node] + cost[node][son];
dad[son] = node;
if(!inq[son]) {
inq[son] = 1;
q[right++] = son; } } } }
return (dist[sink] != INF);
}
inline int pump(double d)
{
int node;
double minflow = INF;
for(node=sink; node!=source; node=dad[node])
minflow = min(minflow, capacity[dad[node]][node] - flow[dad[node]][node]);
if(minflow)
for(node=sink; node!=source; node=dad[node])
flow[dad[node]][node] += minflow, flow[node][dad[node]] -= minflow;
mincost += minflow*dist[sink];
return minflow;
}
inline int computeMaxFlow(double d)
{
double maxflow = 0;
mincost = 0;
while(bellmanford(d)) maxflow += pump(d);
return maxflow;
}
int main()
{
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
int i, j;
double f, ans, step = 1.0, maxdist = -1;
scanf("%d", &n);
for(i=1; i<=n; ++i)
scanf("%lf %lf", &man[i].x, &man[i].y);
for(i=1; i<=n; ++i)
scanf("%lf %lf", &house[i].x, &house[i].y);
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j) {
cost[i][j+n] = mydistance(man[i], house[j]);
maxdist = max(maxdist, cost[i][j+n]);
capacity[i][j+n] = 1;
G[i].push_back(j+n); }
for(i=1; i<=n; ++i) {
G[0].push_back(i);
G[i].push_back(0);
capacity[0][i] = 1; }
for(i=n+1; i<=2*n; ++i) {
G[i].push_back(2*n+1);
G[2*n+1].push_back(i);
capacity[i][2*n+1] = 1;
}
source = 0;
sink = 2*n+1;
while(step*2 <= maxdist) step *= 2;
ans = maxdist;
for(; step>EPS; step *= 0.5)
if(computeMaxFlow(ans-step) == n)
ans -= step;
f = computeMaxFlow(ans);
printf("%lf %lf", ans, mincost);
return 0;
}