Cod sursa(job #1397415)

Utilizator stefanzzzStefan Popa stefanzzz Data 23 martie 2015 15:09:11
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.24 kb
#include <stdio.h>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <string.h>
#include <algorithm>
#include <time.h>
#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;
bool cuplat[MAXN];
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, i;
	totcst = 0;

	memset(fx, 0, sizeof(fx));
	
	while(Bellman_Ford(mx_c)){
		for(i = off + 1; i <= off + n; i++){
			if(dstb[i] != INF && fx[i][fin] < cap[i][fin]){
				a = i;
				while(bk[a] != -1){
					if(fx[bk[a]][a] == cap[bk[a]][a])
						break;
					a = bk[a];
				}

				if(bk[a] != -1)
					continue;
				totfx++;
				totcst += dstb[i];
				
				fx[i][fin]++;
				fx[fin][i]--;
				a = i;
				while(bk[a] != -1){
					fx[bk[a]][a]++;
					fx[a][bk[a]]--;
					a = bk[a];
				}
			}
		}

		/*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, a;

	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;
		}
	
	srand(time(NULL));
	double mxcupl = INF;
	for(int iter = 1; iter <= 10; iter++){
		double mx = 0;
		memset(cuplat, 0, sizeof(cuplat)); 
		for(i = 1; i <= n / 2; i++){
			a = rand() % n + 1;
			while(cuplat[a])
				a = rand() % n + 1;
			cuplat[a] = 1;
			double d = euclidDist(pct[i], ad[a]);
			if(d > mx) mx = d;
		}
		for(j = 1; i <= n; i++){
			while(cuplat[j]) j++;
			double d = euclidDist(pct[i], ad[j++]);
			if(d > mx) mx = d;
		}
		if(mx < mxcupl) mxcupl = INF;
	}

	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 = n - 1, r = dst.size() - 1, mid;

	while(dst[r] > mxcupl + EPS) r--;

	while(l < r){
		mid = (l + r) >> 1;
		if(works(dst[mid])) r = mid - 1;
		else l = mid + 1;
	}
	while(!works(dst[r])) r++;
	
	printf("%.7lf %.7lf\n", dst[r], totcst);

	return 0;
}