# Poj Solution 2333

```http://poj.org/problem?id=2333

#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( "%I64dn", ans/2 );
else
printf( "%I64d.5n", ans/2 );
}

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

return 0;
}
```
This entry was posted in poj. Bookmark the permalink.