1925.txt

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

#include"stdio.h"
#include"math.h"
#include"memory.h"

int x[5010],h[5010];
int pos[1000001];

int n;

void init()
{
	int i;
	scanf( "%d", &n );

	for( i=0; i<n; i++ )
		scanf( "%d %d", x+i, h+i );

	memset( pos, -1, sizeof(int)*(x[n-1]+1) );
}

void doit()
{
	int i,j,l,y,k;
	int ans;

	ans = 100000;
	pos[0] = 0;

	for( i=1; i<n; i++ )
	{
		
		l = x[i] - (int)sqrt( (double)h[i]*h[i] - (double)( h[i] - h[0] )*( h[i] - h[0] ) );

		for(j = l>0?l:0 ; j < x[i] ; j ++ )
		if(pos[j] >=0 )
		{
			y = (x[i]<<1) - j;
			k = pos[j] + 1;

			if( y >= x[n-1] )
			{
				if( k < ans ) ans = k;
			}
			else if( pos[y] < 0 || k < pos[y] ) pos[y] = k;
		}

//		if(i%100==0)
//			printf("::%d\n", i);
	}

	if( ans == 100000 ) ans = -1;

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

int main()
{
	int i,cas;

	scanf( "%d", &cas );
	for( i=1; i<=cas; i++ )
	{
		init();
		doit();
	}

	return 0;