Poj Solution 2173

http://poj.org/problem?id=2173

#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 %dn", bx, by, ans );
}

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 *