2008.txt

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

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

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

bool cmp( const pair<int,int> &a, const pair<int,int> &b ) {
	return a.second < b.second;
}

int main( ) {
	int a, b, c, n, i, j, m, limit, ans = 0;
	scanf( "%d", &n );
	scanf( "%d%d%d", &a, &b, &c );

	for( i=0; i<n; i++ )
		scanf( "%d%d", &p[i].first, &p[i].second );

	sort( p, p+n );
	priority_queue<int, vector<int> > pq;

	for( i=0; i<n; i++ ) {
		m = 0;
		for( j=i; j<n; j++ )
			q[m++] = p[j];
		
		sort( q, q+m, cmp );

		for( j=m-1; j>=0; j-- ) {

			pq.push( a*q[j].first+b*q[j].second );
			limit = a*p[i].first+b*q[j].second+c;

			while( !pq.empty() && pq.top() > limit )
				pq.pop();
			if( pq.size() > ans )
				ans = pq.size();

		}
		while( !pq.empty() )
			pq.pop();
	}

	printf( "%d\n", ans );

	return 0;
}