Pagini recente » Cod sursa (job #2252078) | Cod sursa (job #2081883) | Cod sursa (job #1002801) | Cod sursa (job #2194067) | Cod sursa (job #1402814)
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define ITERATOR vector <int>::iterator
const int NMAX = 405, INF = 2e9;
const double eps = 1.e-3;
vector <int> graph[NMAX * 2], matchGraph[NMAX * 2];
pair <double, double> soldat[NMAX], adapost[NMAX];
int SOURCE, DEST;
int n, gauche[NMAX], droit[NMAX], cap[NMAX * 2][NMAX * 2], flow[NMAX * 2][NMAX * 2], dad[NMAX * 2];
bool vis[NMAX * 2];
double lim, mid, dist[NMAX][NMAX], dmin[NMAX * 2], cost[NMAX * 2][NMAX * 2];
bool pairUp (int node) {
if(vis[node])
return 0;
vis[node] = 1;
for(ITERATOR it = matchGraph[node].begin(); it != matchGraph[node].end(); ++ it) {
if(dist[node][*it] > mid)
continue;
if(!gauche[*it] || pairUp(gauche[*it])) {
gauche[*it] = node;
droit[node] = *it;
return 1;
}
}
return 0;
}
int cuplaj () {
int i, j, ans, change;
for(i = 1; i <= n; ++ i) {
matchGraph[i].clear();
gauche[i] = droit[i] = 0;
}
for(i = 1; i <= n; ++ i)
for(j = 1; j <= n; ++ j)
if(dist[i][j] < mid)
matchGraph[i].push_back(j);
change = 1;
while(change) {
change = 0;
memset(vis, 0, sizeof(vis));
for(i = 1; i <= n; ++ i)
if(!droit[i] && pairUp(i))
change = 1;
}
ans = 0;
for(i = 1; i <= n; ++ i)
if(droit[i])
++ ans;
return ans;
}
double bs (double left, double right) {
double last;
int step;
for(step = 1; step <= 60; ++ step) {
mid = (left + right) * 0.5;
if(cuplaj() == n) {
last = mid;
right = mid;
}
else
left = mid;
}
return last;
}
double sqr (double x) {
return x * x;
}
void drawEdge (int a, int b, double costAB) {
graph[a].push_back(b);
graph[b].push_back(a);
cap[a][b] = 1;
cost[a][b] = costAB;
cost[b][a] = -costAB;
}
void buildGraph () {
int i, j;
SOURCE = 0;
DEST = 2 * n + 1;
for(i = 1; i <= n; ++ i)
drawEdge(SOURCE, i, 0);
for(i = 1; i <= n; ++ i)
for(j = n + 1; j <= 2 * n; ++ j)
if(dist[i][j - n] <= lim)
drawEdge(i, j, dist[i][j - n]);
for(i = n + 1; i <= 2 * n; ++ i)
drawEdge(i, DEST, 0);
}
bool bellmanFord() {
queue <int> q;
int node, i;
ITERATOR it;
for(i = SOURCE; i <= DEST; ++ i) {
dmin[i] = INF - eps;
vis[i] = dad[i] = 0;
}
q.push(SOURCE);
vis[SOURCE] = 1;
dmin[SOURCE] = 0;
while(!q.empty()) {
node = q.front();
q.pop();
vis[node] = 0;
if(node == DEST)
continue;
for(it = graph[node].begin(); it != graph[node].end(); ++ it)
if(flow[node][*it] < cap[node][*it] && dmin[node] + cost[node][*it] < dmin[*it]) {
dmin[*it] = dmin[node] + cost[node][*it];
dad[*it] = node;
if(!vis[*it]) {
q.push(*it);
vis[*it] = 1;
}
}
}
return dmin[DEST] < INF - eps;
}
double maxFlow() {
ITERATOR it;
int minFlow, node;
double ans;
ans = 0;
while(bellmanFord()) {
node = DEST;
minFlow = INF;
while(node != SOURCE) {
minFlow = min(minFlow, cap[dad[node]][node] - flow[dad[node]][node]);
node = dad[node];
}
node = DEST;
while(node != SOURCE) {
flow[dad[node]][node] += minFlow;
flow[node][dad[node]] -= minFlow;
node = dad[node];
}
ans += minFlow * dmin[DEST];
}
return ans;
}
int main() {
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
int i, j;
scanf("%d", &n);
for(i = 1; i <= n; ++ i)
scanf("%lf%lf", &soldat[i].first, &soldat[i].second);
for(i = 1; i <= n; ++ i)
scanf("%lf%lf", &adapost[i].first, &adapost[i].second);
for(i = 1; i <= n; ++ i)
for(j = 1; j <= n; ++ j)
dist[i][j] = sqrt(sqr(soldat[i].first - adapost[j].first) + sqr(soldat[i].second - adapost[j].second));
lim = bs(0, 5000);
buildGraph();
printf("%lf %lf\n", lim, maxFlow());
return 0;
}