2333.txt

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

#include <stdio.h>

const int size = 5010;

struct point
{
	int x, y;
}p[size], pt[size];

__int64 s[size];

inline __int64 cross( point &o, point &a, point &b )
{
	return (__int64)(a.x-o.x)*(b.y-o.y) - (__int64)(a.y-o.y)*(b.x-o.x);
}

inline __int64 dis( point &a, point &b )
{
	return (__int64)(a.x-b.x)*(a.x-b.x) + (__int64)(a.y-b.y)*(a.y-b.y);
}

int n, l;

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

	for( i=0; i<n; i++ )
	{
		scanf( "%d %d", &p[i].x, &p[i].y );
		p[i].y = 1000010 - p[i].y;
		pt[i].x = p[i].x;
		pt[i].y = 0;
	}

	s[0] = 0;
	for( i=1; i<n; i++ )
	{
		s[i] = s[i-1] + (__int64)( p[i].x - p[i-1].x ) * ( p[i].y + p[i-1].y );
	}

}

void doit( )
{
	int i, j, k, t;
	__int64 ans = 0, temp, ll;

	for( i=0; i<n; i++ )
	{
		t = p[i].x + l;
		ll = (__int64) l* l;
		
		k=i+1;

		for( j=i+1; j<n && p[j].x <= t; j++ )
			if( cross( p[k], p[i], p[j] ) <= 0 && dis( p[i], p[j] ) <= ll )
			{
				k = j;
				temp =  (__int64)( p[j].x - p[i].x ) * ( p[j].y + p[i].y ) - ( s[j] - s[i] );
				if( temp > ans )
					ans = temp;
			}
	}

	if( ans % 2 == 0 )
		printf( "%I64d\n", ans/2 );
	else
		printf( "%I64d.5\n", ans/2 );
}

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

	return 0;
}