3141.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3141  User Id:fzk 
Memory:28K  Time:62MS
Language:C++  Result:Accepted

Source 

#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: %d\n", ++count, ans );
	}
	return 0;
}