2296.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <memory.h>
#include <stdio.h>
#include <math.h>
struct point
{
	int x, y;
};
int len;
inline bool edge( point &a, point &b )
{
	return abs(a.x-b.x)<len && abs(a.y-b.y)<len;
}
bool sign[100];
point p[100], lab[100];
int n;
void change( int a )
{
	if( lab[a].y == p[a].y - len/2 )
		lab[a].y = p[a].y + len/2;
	else
		lab[a].y = p[a].y - len/2;
}
bool search( int a )
{
	int i;
	sign[a] = true;
	change( a );
	for( i=0; i<n; i++ )
	if( i != a && edge( lab[a], lab[i] ) )
	{
		if( sign[i] || !search( i ) )
			break;
	}
	return i == n;	
}
bool adjust( int a )
{
	int i;
	memset( sign, 0, sizeof sign );
	sign[a] = true;

	for( i=0; i<n; i++ )
	if( i != a && edge( lab[a], lab[i] ) )
	{
		if( sign[i] || !search( i ) )
			break;
	}
	if( i == n )
		return true;	
	change( a );
	memset( sign, 0, sizeof sign );
	sign[a] = true;
	for( i=0; i<n; i++ )
	if( i != a && edge( lab[a], lab[i] ) )
	{
		if( sign[i] || !search( i ) )
			break;
	}
	return i == n;
}
bool judge( )
{
	int i;
	for( i=0; i<n; i++ )
		lab[i].y = p[i].y + len/2;
	for( i=0; i<n; i++ )
		if( !adjust( i ) )
			return false;	
	return true;
}
void init( )
{
	int i;
	scanf( "%d", &n );
	for( i=0; i<n; i++ )
	{
		scanf( "%d %d", &p[i].x, &p[i].y );
		
		p[i].x *= 2;
		p[i].y *= 2;

		lab[i].x = p[i].x;
	}
}
int main( )
{
	int cas, a, b, c;
	scanf( "%d", &cas );
	while( cas-- )
	{
		init( );
		a = 1; b =20010;
		while( b - a > 1 )
		{
			c = (b+a)/2;
			len = c*2;
			if( judge() )
			a = c;
			else b = c;
		}
		printf( "%d\n", a );
	}
	return 0;
}