OJ Board

Code: Select all

double x = 0.085;
double m = pow( 10.0, d );
x = (int)(x * m + 0.5) / m;

Code: Select all

		if(m != k && n != 0)
		{
			while(fabs(start-end) > EPS)
			{
				middle = (start+end)/2;
				
				/* Build Bipartite graph using matching condition d<=middle */
				for(i=0;i<=m;i++)
				{
					for(j=0;j<=n;j++)
						cap[i][j] = 0;
				}	
				
				for(i=0;i<m;i++)
				{
					for(j=0;j<n;j++)
					{
						d = hypot(xg[i]-xh[j], yg[i]-yh[j]);
						
						if(d <= middle)	cap[i][j] = 1;
					}
				}	
				
				n_right_side = m;	n_left_side = n;
				
				max = Bipartite();
				
				if(max >= m-k)		end   = middle;
				else				start = middle;
			}
		}

		cout<<"Case #"<<l<<":\n";

		if(m == k)	
			cout<<0<<"\n";
		else if(n == 0)
			cout<<"Too bad.\n";
		else		
			cout<<middle+EPS<<"\n";

Code: Select all

#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
#include <math.h>

using namespace std;

#define NIL -1
#define MAXN 110

typedef struct Point_
{
	double x,y;
} Point_;

double maxDis;
int Match[MAXN];
int v,M,N;
double W[MAXN][MAXN];
bool visited[MAXN];
vector <int> adj[MAXN];
Point_ field[MAXN];


bool augment(int u)
{
	int next;
	if( u == -1 ) 
		return true;

	for( int i = 0; i < adj[u].size(); i++ )
	{
		next = adj[u][i];
		if( !visited[next] )
		{
			visited[next] = true;
			if(augment(Match[next]))
			{
				Match[next] = u;
				return true;
			}
		}
	}

	return false;
}


int MBM(double w)
{
	int i,match,j;

	memset(Match,NIL,sizeof(Match));

	for( i = 1; i <= M; i++ ) adj[i].clear();
		
	for( i = 1; i <= M; i++ )
	{
		for( j = M + 1; j < N + M + 1; j++ )
		{
			if( W[i][j] <= w ) adj[i].push_back(j);
		}
	}

	match = 0;

	for( i = 1; i <= M; i++ ) 
	{
		memset(visited,false,sizeof(visited));
		if( augment(i) ) 
			match++;
	}

	return match;
}


void buildGraph()
{
	int i,j;
	v = N + M + 2;
	maxDis = -1;

	for( i = 1; i <= M; i++ )
	{
		for( j = M + 1; j < N + M + 1; j++ )
		{
			W[i][j] = sqrt((field[i].x - field[j].x) * (field[i].x - field[j].x) + (field[i].y - field[j].y) * (field[i].y - field[j].y) );
			if( maxDis < W[i][j] ) 
				maxDis = W[i][j];
		}
	}

}


int main()
{
	int i,K,T,caseno,m;
	double lo,hi,mid;
	
	//freopen("C:\\4.txt","rb",stdin);

	scanf("%d",&T);
	
	for( caseno = 1; caseno <= T; caseno++ )
	{
		scanf("%d %d %d",&M,&N,&K);

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

		printf("Case #%d:\n",caseno);
		if( M == K ) 
		{
			printf("0\n\n");
			continue;
		}


		buildGraph();
		
		m = MBM(maxDis);
		if( m < M - K ) 
		{
			printf("Too bad.\n\n");
			continue;
		}

		lo = 0,hi = maxDis;

		while( fabs(lo - hi) > 1e-7 )
		{
			mid = (lo + hi) / 2;
			m = MBM(mid);
			if( m >= M - K ) hi = mid;
			else lo = mid;
		}
		
		double mm = 1000.0;
		mid = (int)(mid * mm + 0.5) / mm;
		printf("%.3lf\n\n",mid);
	}

	return 0;
}