# 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, x, y, m;

point p;

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;

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.