Cod sursa(job #343154)

Utilizator CezarMocanCezar Mocan CezarMocan Data 25 august 2009 10:37:40
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <cstdio>
#include <math.h>
#include <vector>
#include <cstring>
#include <algorithm>
#define maxn 805
#define inf 0x3f3f3f3f

using namespace std;

struct punct {
	int x, y;
};

int n, i, j;
double aa, bb;
punct v[2 * maxn];
int viz[2 * maxn], cup_st[2 * maxn], cup_dr[2 * maxn];
int dist_min, cost_min;
int dist[2 * maxn][2 * maxn];
int cb[maxn * maxn], nr;
int ok;
vector <int> g[maxn];


inline int distanta(punct a, punct b) {
	return (int) sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}

inline int min(int a, int b) {
	if (a < b)
		return a;
	return b;
}

inline void build_graf(int dmax) {
	int i, j;
	for (i = 1; i <= 2 * n; i++)
		g[i].clear();
	for (i = 1; i <= n; i++) {
		for (j = n + 1; j <= 2 * n; j++) 
			if (dist[i][j] <= dmax) {
				g[i].push_back(j);
			}
	}
		
}

void cupleaza(int nod, int pt) {
	int i, fiu;

	if (viz[nod])
		return;
	viz[nod] = 1;

	if (pt == 0) {
		for (i = 0; i < g[nod].size(); i++) {
			fiu = g[nod][i];
			cupleaza(fiu, 1);
			if (ok) {
				cup_st[nod] = fiu;
				cup_dr[fiu] = nod;
				return;
			}
		}
	}

	else {
		if (cup_dr[nod]) 
			cupleaza(cup_dr[nod], 0);
		else {
			ok = 1;
			return;
		}
	}
}

inline bool posibil(int dmax) {
	int i, nr = 0;
	build_graf(dmax);

	memset(cup_st, 0, sizeof(cup_st));
	memset(cup_dr, 0, sizeof(cup_dr));

	for (i = 1; i <= n; i++) 
		if (!cup_st[i]) {
			ok = 0;
			memset(viz, 0, sizeof(viz));
			cupleaza(i, 0);
			nr += ok; 
		}

	if (nr == n)
		return true;
	return false;

}

void bsearch(int left, int right) {
	int m;
	while (left <= right) {
		m = (left + right) / 2;
		if (posibil(cb[m])) {
			dist_min = min(dist_min, cb[m]);
			right = m - 1;
		}
		else
			left = m + 1;
	}
}

inline void afis(int nr) {
	printf("%d.", nr / 100000);
	int aux = nr % 100000;
	if (aux)
		while (aux < 10000) {
			printf("0");
			aux *= 10;
		}
	printf("%d ", nr % 100000);
}

int main() {
	freopen("adapost.in", "r", stdin);
	freopen("adapost.out", "w", stdout);

	scanf("%d", &n);
	for (i = 1; i <= 2 * n; i++) {
		scanf("%lf%lf", &aa, &bb);
		v[i].x = (int) (aa * 100000);
		v[i].y = (int) (bb * 100000);
	}

	dist_min = inf;
	for (i = 1; i <= n; i++)
		for (j = n + 1; j <= 2 * n; j++) {
			dist[i][j] = distanta(v[i], v[j]);
			dist[j][i] = dist[i][j];
			nr++;
			cb[nr] = dist[i][j];
		}

	sort(cb + 1, cb + nr + 1);

	bsearch(1, nr);
	afis(dist_min);
	afis(0);
	

	return 0;
}