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.

Leave a Reply

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