Cod sursa(job #18001)

Utilizator love_for_uSpancioc Riana love_for_u Data 17 februarie 2007 21:03:07
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.38 kb

#include<stdio.h>
#include<string.h>
#include <math.h>
#include <vector>
#include <algorithm>
#define PB push_back
#define MP make_pair
#define EPS 1e-6
#define ABS(a) ( (a) < 0 ? -(a) : (a) )
#define MIN(a, b) ( (a) < (b) ? (a) : (b) )
#define NMAX 825
#define INF 100000001

using namespace std;

vector <double> Dist;
vector <int> Adj[NMAX];
vector <double> Cost[NMAX];

struct per { double x, y; } V[NMAX];

int L[NMAX], R[NMAX], U[NMAX];
int P[NMAX];
int C[NMAX][NMAX], F[NMAX][NMAX];
int N, NN;
int i, j, Nr, FLX;
int l, r, c;

double cost_, CST, minc, minm;

void unite(int x, int y, double z, int capa)
{
        C[x][y] = capa;
        
		Adj[x].PB(y);
		Cost[x].PB(z), Cost[y].PB(-z);
}

int PairUp(int x, double c_max)
{
	int i;
	int sz = Adj[x].size();
	
	if (U[x]) return 0;
	
	U[x] = 1;

	for (i = 0; i < sz; i++)
		if ( Cost[x][i] < c_max || ABS( Cost[x][i] - c_max) < EPS )
			if ( R[Adj[x][i]] == -1 || PairUp(R[Adj[x][i]], c_max) )
			{
				R[L[x] = Adj[x][i]] = x;
			
				return 1;
			}
			
	return 0;
}

int augment(double c_max)
{
	memset(L, 0xFF, sizeof(L));
	memset(R, 0xFF, sizeof(R));
	memset(U, 0xFF, sizeof(U));

	for (i = 1; i <= NN; i ++)
		if (!PairUp(i, c_max))
		{
			memset(U, 0, sizeof(U));
			PairUp(i, c_max);
		}

	int Ans = 0;
	
	for (i = 1; i <= NN; i ++)
		if (L[i] != -1) ++ Ans;
	
	return Ans;
}

int main()
{

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

	scanf("%d", &N);

	NN = 2 * N;

	for (i = 1; i <= NN; i++) scanf("%lf %lf", &V[i].x, &V[i].y);

	//for (i = 1; i <= N; i++) unite(0, i, 0.0, 1);

	for (i = 1; i <= N; i++)
		for (j = N + 1; j <= NN; j++)
		{
			cost_ = sqrt( (V[j].x - V[i].x) * (V[j].x - V[i].x) + (V[j].y - V[i].y) * (V[j].y - V[i].y) );
			
			Dist.PB(cost_);
			
			unite(i, j, cost_, 1);
		}
		
	//for (i = N + 1; i <= NN; i++) unite(i, NN + 1, 0.0, 1);
	 
	/*for (i = 1; i <= NN; i++)
	{
			int size = Adj[i].size();
			
			for (j = 0; j < size; j++)
				printf("%d %lf     ",  Adj[i][j], Cost[i][j]);
		
			printf("\n");
			
	}*/
	
	sort(Dist.begin(), Dist.end());
	
	
	
	l = 0, r = Dist.size() - 1;
	
	minm = INF;
	
	while (l <= r)
	{ 
		c = (l + r) / 2;
		
		FLX = augment(Dist[c]);
		
		if (FLX == N) r = c - 1, minm = MIN(Dist[c], minm);
		else 		  l = c + 1;
	}
	
	printf("%.5lf\n", minm);
	
	return 0;
}



























/*#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;

#define NMAX 10005 

vector<int> adj[NMAX];
int l[NMAX], r[NMAX], u[NMAX];
int N, M, i, j, k;

int PairUp(int x)
{
	if (u[x]) return 0;
	u[x] = 1;

	for (vector<int>::iterator it = adj[x].begin(); it != adj[x].end(); it ++)
		if (r[*it] == -1 || PairUp(r[*it]))
		{
			r[l[x] = *it] = x;
			return 1;
		}
	return 0;
}

int main(void) {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	scanf("%d %d", &N, &M);
	for (k = 0; k < M; k ++)
	{
		scanf("%d %d", &i, &j);
		adj[i].push_back(j);
	}	

	memset(l, 0xFF, sizeof(l));
	memset(r, 0xFF, sizeof(r));
	memset(u, 0xFF, sizeof(u));

	for (i = 0; i < N; i ++)
		if (!PairUp(i))
		{
			memset(u, 0, sizeof(u));
			PairUp(i);
		}

	int Ans = 0;
	for (i = 0; i < N; i ++)
		if (l[i] != -1)
			++ Ans;
	printf("%d\n", Ans);
	
	return 0;
}*/