Cod sursa(job #676172)

Utilizator darrenRares Buhai darren Data 8 februarie 2012 19:57:28
Problema Adapost Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <cmath>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define x first
#define y second

const double eps = 0.0001;
const int INF = 0x3f3f3f3f;

int N;
pair<double, double> A[402], B[402];
bool inQ[802];
int C[802][802], F[802][802], T[802], times;
double sumdist, D[802];
queue<int> Q;

inline double pow2(double val)
{
	return val * val;
}
inline double getDistance(int i1, int i2)
{
	return sqrt(pow2(A[i1].x - B[i2].x) + pow2(A[i1].y - B[i2].y));
}
inline double psDistance(int i1, int i2)
{
	if (i1 == 0 || i1 == 2 * N + 1 || i2 == 0 || i2 == 2 * N + 1) return 0;
	if (i2 > N) return getDistance(i1, i2 - N);
	return -getDistance(i2, i1 - N);
}

bool findPath()
{
	memset(inQ, 0, sizeof(inQ));
	while (!Q.empty()) Q.pop();
	for (int i = 0; i <= 2 * N + 1; ++i)
		D[i] = INF;
	
	Q.push(0);
	inQ[0] = true;
	D[0] = 0;
	while (!Q.empty())
	{
		int now = Q.front();
		Q.pop();
		inQ[now] = false;
		
		for (int i = 0; i <= 2 * N + 1; ++i)
			if (C[now][i] > F[now][i] && D[now] + psDistance(now, i) < D[i])
			{
				D[i] = D[now] + psDistance(now, i);
				T[i] = now;
				
				if (!inQ[i])
				{
					inQ[i] = true;
					Q.push(i);
				}
			}
	}
	
	if (D[2 * N + 1] == INF) return false;
	
	//printf("%d\n", times);
	
	++times;
	for (int i = 2 * N + 1; i != 0; i = T[i])
	{
		//printf("%d %d\n", T[i], i);
		++F[T[i]][i], --F[i][T[i]];
		sumdist += psDistance(T[i], i);
	}
	return true;
}

void clearAll()
{
	times = 0;
	sumdist = 0;
	memset(C, 0, sizeof(C));
	memset(F, 0, sizeof(F));
}
bool ok(double now)
{
	clearAll();
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			if (now - getDistance(i, j) > eps)
				C[i][N + j] = 1;
	for (int i = 1; i <= N; ++i)
	{
		C[0][i] = 1;
		C[N + i][2 * N + 1] = 1;
	}
	
	while (findPath());
	
	if (times == N)
		return true;
	return false;
}

int main()
{
	ifstream fin("adapost.in");
	ofstream fout("adapost.out");
	
	fin >> N;
	for (int i = 1; i <= N; ++i)
		fin >> A[i].x >> A[i].y;
	for (int i = 1; i <= N; ++i)
		fin >> B[i].x >> B[i].y;
	
	double lim1 = 0, lim2 = 2000;
	while (lim2 - lim1 >= eps)
	{
		double mid = (lim1 + lim2) / 2;
		bool resultnow = ok(mid);
		
		if (resultnow)
			lim2 = mid;
		else
			lim1 = mid;
	}
	
	ok(lim2);
	fout << fixed << setprecision(4) << lim2;
	fout << ' ';
	fout << fixed << setprecision(4) << sumdist;
	fout << '\n';
	
	fin.close();
	fout.close();
}