2173.txt

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

#include <stdio.h>
#include <memory.h>
#include <algorithm>

using namespace std;

typedef pair<int,int> point;
int w, h, n;
int a[110], x[110], y[110], m;

point p[110];

void init( )
{
	int i, xx, yy;
	m = 0;
	n = 0;

	scanf( "%d %d %d", &n, &w, &h );

	a[m++] = 0, a[m++] = h;

	for( i=0; i<n; i++ )
	{
		scanf( "%d %d", &xx, &yy );
		p[i] = point( xx, yy );
		a[m++] = yy;
	}
	
	p[n] = point( w, h );
	n++;

	sort( a, a+m );
	m = unique_copy( a, a+m, a ) - a;
	
	sort( p, p+n );
}

int left[110];

void doit( )
{
	int i, j, k, ans=0, bx, by, t, l, xx;
	
	memset( left, 0, sizeof left );

	for( i=0; i<n; i=j )
	{
		xx = p[i].first;
		for( j=0; j<m; j++ )
		{
			t = xx;
			for( k=j+1; k<m; k++ )
			{
				l = t;
				if( l > a[k]-a[j] )
					l = a[k]-a[j];

				if( l > ans )
				{
					ans = l;
					bx = xx-l;
					by = a[j];
				}
				
				if( xx - left[k] < t )
					t = xx - left[k];
			}
		}

		for( j=i; p[i].first == p[j].first; j++ )
		{
			k = lower_bound( a, a+m, p[j].second ) - a;
			left[ k ] = p[i].first;
		}
	}

	printf( "%d %d %d\n", bx, by, ans );
}

int main( )
{
	init( );
	doit( );

	return 0;
}