# Poj Solution 3141

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

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

pair<int,int> p[100], q[100];

int n;

bool input( ) {
int i;
scanf( "%d", &n );
if( n == 0 )
return false;
for( i=0; i<n; i++ )
scanf( "%d%d", &p[i].first, &p[i].second );
sort( p, p+n );
return true;
}

int clac( pair<int,int> p[], int len, int a, int b ) {
int i, j;
int best = 0, curr, edge = 0, temp, inside, ans = 0;
for( i=0; i<len; i=j ) {
inside = 0;
temp = edge;
for( j=i; j<len && p[j].first == p[i].first; j++ )
if( p[j].second != a && p[j].second != b )
inside++;
else
edge ++;
curr = edge + inside;
if( curr - best > ans )
ans = curr - best;
if( temp - inside < best )
best = temp - inside;
}
return ans;
}

int main( ) {
int k=0, t, i, j, ans = 0, a, b, count=0, m;
while( input() ) {
ans = 1;
for( i=0; i<n; i++ ) {
for( j=i+1; j<n; j++ ) {
a = p[i].second;
b = p[j].second;
if( a > b ) swap( a, b );

m = 0;

for( k=0; k<n; k++ )
if( p[k].second >= a && p[k].second <= b )
q[m++] = p[k];

t = clac( q, m, a, b );
if( t > ans )
ans = t;
}
}
printf( "Case %d: %dn", ++count, ans );
}
return 0;
}

```
This entry was posted in poj. Bookmark the permalink.