Cod sursa(job #1397387)

Utilizator stefanzzzStefan Popa stefanzzz Data 23 martie 2015 14:42:54
Problema Adapost Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <stdio.h>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <string.h>
#include <algorithm>
#define MAXN 420
#define INF 1e5
#define EPS 1e-6
#define x first
#define y second
using namespace std;

const int off = 405, start = 0, fin = 402;
int n, cap[2 * MAXN][2 * MAXN], fx[2 * MAXN][2 * MAXN], bk[2 * MAXN];
double totcst;
vector<double> dst;
pair<double, double> pct[MAXN], ad[MAXN];
vector< pair<int, double> > G[2 * MAXN];
double dstb[2 * MAXN];

inline double euclidDist(pair<double, double> a, pair<double, double> b){
	double dx = a.x - b.x, dy = a.y - b.y;
	return sqrt(dx * dx + dy * dy);
}

bool Bellman_Ford(double mx_c){
	int i, a;
	bool uzq[2 * MAXN];
	queue<int> q;

	for(i = 0; i <= n + off; i++){
		dstb[i] = INF;
		bk[i] = -1;
		uzq[i] = 0;
	}

	dstb[start] = 0;
	q.push(start); uzq[start] = 1;
	while(!q.empty()){
		a = q.front(); q.pop();
		uzq[a] = 0;
		for(auto b: G[a]){
			if(fabs(b.second) < mx_c + EPS && fx[a][b.first] < cap[a][b.first] && dstb[a] + b.second < dstb[b.first]){
				dstb[b.first] = dstb[a] + b.second;
				bk[b.first] = a;
				if(!uzq[b.first]){ uzq[b.first] = 1; q.push(b.first); }
			}
		}
	}
	
	return dstb[fin] < INF;
}

bool works(double mx_c){
	int totfx = 0, a;
	totcst = 0;

	memset(fx, 0, sizeof(fx));
	
	while(Bellman_Ford(mx_c)){
		totfx++;
		totcst += dstb[fin];
		a = fin;
		while(bk[a] != -1){
			fx[bk[a]][a]++;
			fx[a][bk[a]]--;
			a = bk[a];
		}
	}

	return (totfx == n);
}

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", &pct[i].x, &pct[i].y);
	for(i = 1; i <= n; i++)
		scanf("%lf %lf", &ad[i].x, &ad[i].y);
	
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++){
			dst.push_back(euclidDist(pct[i], ad[j]));
			G[i].push_back(make_pair(j + off, dst.back()));
			G[j + off].push_back(make_pair(i, -dst.back()));
			cap[i][j + off] = 1;
		}

	sort(dst.begin(), dst.end());

	for(i = 1; i <= n; i++){
		cap[start][i] = cap[i + off][fin] = 1;
		G[start].push_back(make_pair(i, 0));
		G[i + off].push_back(make_pair(fin, 0));
	}
	
	int l = 0, r = dst.size() - 1, mid; 
	
	while(l < r){
		mid = (l + r) >> 1;
		if(works(dst[mid])) r = mid - 1;
		else l = mid + 1;
	}
	while(r < 0 || !works(dst[r])) r++;
	
	printf("%.7lf %.7lf\n", dst[r], totcst);

	return 0;
}