Cod sursa(job #48152)

Utilizator TYTUSVlad Saveluc TYTUS Data 4 aprilie 2007 14:08:05
Problema Adapost Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.69 kb
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cmath>
#include <deque>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<double, double>point;

const int NMAX = 401;
const double eps = 1.0e-3;
const double infiF = 1.0e7;

point s[NMAX], ad[NMAX];
double d[NMAX][NMAX];
int cap[2 * NMAX][2 * NMAX];
vector<int>lv[2 * NMAX];

double pot[2 * NMAX]; //Potential;
double dd[2 * NMAX]; //Distanta din dijkstra
double dai[20 * NMAX]; //Arbore de intervale pt Dijkstra
int wNod[20 * NMAX]; //Arbore din intervale pt Dijkstra

int n;

inline double costwP(int a, int b) { //Costul unei muchii fara potentiale
	if (a == 0 || a == 2 * n + 1) {
		return 0.0;
	}
	if (b == 0 || b == 2 * n + 1) {
		return 0.0;
	}
	if (a < b) {
		return d[a][b - n];
	} else {
		return -d[b][a - n];
	}
}
	
inline double cost(int a, int b) {
	/*
	if (pot[a] - pot[b] + costwP(a, b) < 0.0) {
		printf ("Muchia de la %d la %d costul este %lf - %lf + %lf = %lf\n", a, b, pot[a], pot[b],
				costwP(a, b), pot[a] - pot[b] + costwP(a, b));
	}
 	assert(pot[a] - pot[b] + costwP(a, b) >= 0.0);*/
	return pot[a] - pot[b] + costwP(a, b);
}

void update(int n, double newVal, int nod, int l, int r) { //Update-ul pe AIB
	if (l > n || r < n) {
		return;
	}
	if (l == r) {
		dai[nod] = newVal;
		wNod[nod] = l;
		return;
	}
	int mid = (l + r)>>1;
	update(n, newVal, nod<<1, l, mid);
	update(n, newVal, nod * 2 + 1, mid + 1, r);
	if (dai[2 * nod] < dai[2 * nod + 1]) {
		dai[nod] = dai[2 * nod];
		wNod[nod] = wNod[2 * nod];
	} else {
		dai[nod] = dai[2 * nod + 1];
		wNod[nod] = wNod[2 * nod + 1];
	}
}

inline double sqr(double x) {
	return x * x;
}

int pi[2 * NMAX], q[2 * NMAX];
int bf() {
	int l, r;
	q[0] = 0;
	memset(pi, -1, 8 * NMAX);
	pi[0] = 0;
	for (l = 0, r = 1; l < r; ++l) {
		vector<int>::iterator it;
// 		printf ("%d\n", q[l]);
		for (it = lv[q[l]].begin(); it != lv[q[l]].end(); ++it) {
			if (cap[q[l]][*it] && pi[*it] == -1) {
// 				printf ("--%d\n", *it);
				q[r++] = *it;
				pi[*it] = q[l];
				if ((*it) == 2 * n + 1) {
					return 1;
				}
			}
		}
	}
	return 0;
}
	
void build(double lim) {
	int i, j;
	lv[0].clear();
	lv[2 * n + 1].clear();
	for (i = 1; i <= n; ++i) {
		lv[i].clear();
		lv[0].push_back(i);
		lv[i].push_back(0);
		lv[n + i].clear();
		lv[n + i].push_back(2 * n + 1);
		lv[2 * n + 1].push_back(n + i);
	}
	
	for (i = 1; i <= n; ++i) {
		cap[0][i] = 1;
		cap[i][0] = 0;
		cap[n + i][2 * n + 1] = 1;
		cap[2 * n + 1][n + i] = 0;
		for (j = 1; j <= n; ++j) {
			if (d[i][j] <= lim) {
				cap[i][n + j] = 1;
				lv[i].push_back(n + j);
				lv[n + j].push_back(i);
			} else {
				cap[i][n + j] = 0;
			}
			cap[n + j][i] = 0;
		}
	}
}
	

int flow(double lim) {
	int i, j, ret = 0;
	build(lim);
	//Pun muchii cu greedy
	for (i = 1; i <= n; ++i) {
		for (j = n + 1; j <= 2 * n; ++j) {
			if (cap[i][j] && cap[j][2 * n + 1]) {
				cap[0][i] = 0;
				cap[i][0] = 1;
				cap[i][j] = 0;
				cap[j][i] = 1;
				cap[j][2 * n + 1] = 0;
				cap[2 * n + 1][j] = 1;
				ret++;
				break;
			}
		}
	}
	//Fluxul propriu-zis
	while (bf()) {
		int nod = 2 * n + 1;
		while (nod != 0) {
//  			printf ("Nod = %d\n", nod);
			cap[nod][pi[nod]] = 1;
			cap[pi[nod]][nod] = 0;
			nod = pi[nod];
		}
		ret++;
	}
	return ret >= n ? 1 : 0; //De fapt era ret == n ? 1 : 0
}

void dijkstra() {
	int used[2 * NMAX], i;
	dd[0] = 0.0;
	pi[0] = 1;
	used[0] = 0;
	for (i = 1; i <= 2 * n + 1; ++i) {
		dd[i] = infiF;
		pi[i] = -1;
		used[i] = 0;
	}
	for (i = 1; i <= 2 * n + 1; ++i) {
		int nod = -1;
		double cmin = infiF + 1.0;
		int j;
		for (j = 0; j <= 2 * n + 1; ++j) {
			if (!used[j] && dd[j] < cmin) {
				cmin = dd[j];
				nod = j;
			}
		} //Ok. Am aflat nodul minim
		used[nod] = 1;
		vector<int>::iterator it;
		for (it = lv[nod].begin(); it != lv[nod].end(); ++it) {
			if (cap[nod][*it] && dd[nod] + cost(nod, *it) < dd[*it]) {
				dd[*it] = dd[nod] + cost(nod, *it);
				pi[*it] = nod;
			}
		}
	}
}


double cuplaj(double lim) {
	build(lim);
	int i;
	pot[0] = 0.0;
	for (i = 1; i <= 2 * n + 1; ++i) {
		pot[i] = infiF;
	}
	deque<int>dq;
	dq.push_back(0);
	for (; dq.size(); dq.pop_front()) {
		int nod = dq.front();
// 		printf ("pot[%d] = %lf\n", nod, pot[nod]);
		vector<int>::iterator it;
		for (it = lv[nod].begin(); it != lv[nod].end(); ++it) {
			if (cap[nod][*it] && pot[nod] + costwP(nod, *it) < pot[*it]) {
				pot[*it] = pot[nod] + costwP(nod, *it);
				dq.push_back(*it);
			}
		}
	}
// 	cout<<"Am calculat potentialele initiale"<<endl;
	for (i = 1; i <= n; ++i) {
// 		printf ("UNu\n");
		dijkstra();
		int nod = 2 * n + 1; 
		while (nod != 0) {
			cap[nod][pi[nod]] = 1;
			cap[pi[nod]][nod] = 0;
// 			pot[nod] += dd[nod];
			nod = pi[nod];
		}
// 		pot[nod] += dd[nod];
		int j;
		for (j = 0; j <= 2 * n + 1; ++j) {
			pot[j] += dd[j];
		}
	}
	double ret = 0.0;
	for (i = 1; i <= n; ++i) {	
		vector<int>::iterator it;
		for (it = lv[i].begin(); it != lv[i].end(); ++it) {
			if (cap[i][*it] == 0) {
				ret += d[i][(*it) - n];
			}
		}
	}
	return ret;
}
	

int main() {
	FILE *fin = fopen ("adapost.in", "r");
	FILE *fout = fopen ("adapost.out", "w");
	fscanf (fin, "%d", &n);
	int i, j;
	for (i = 1; i <= n; ++i) {
		fscanf (fin, "%lf %lf", &s[i].first, &s[i].second);
	}
	for (i = 1; i <= n; ++i) {
		fscanf (fin, "%lf %lf", &ad[i].first, &ad[i].second);
	}
	vector<double>allV;
	for (i = 1; i <= n; ++i) {
		for (j = 1; j <= n; ++j) {
			d[i][j] = sqrt(sqr(s[i].first - ad[j].first) + sqr(s[i].second - ad[j].second));
			allV.push_back(d[i][j]);
		}
	}
	sort(allV.begin(), allV.end());
	int sol = allV.size() - 1, step;
	for (step = 1; (step << 1) < allV.size(); step <<=1);
	for (; step; step>>=1) {
		if (sol - step >= 0 && flow(allV[sol - step])) {
			sol -= step;
		}
	}
	fprintf (fout, "%lf %lf\n", allV[sol], cuplaj(allV[sol]));
	fclose(fout);
	return 0;
}