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.

Leave a Reply

Your email address will not be published. Required fields are marked *