2382.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2382 on 2006-09-30 at 23:18:04 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1024;

class Cow {
public:
	int h, w, s, wo;
	void make(int a, int b, int c) { scanf("%d %d", &h, &w); s = a*h+b*w-c; }
	bool legal(int mh, int mw) const { return mh <= h && mw <= w; }
};

bool cmp1(const Cow& c1, const Cow& c2) { return c1.w < c2.w; }
bool cmp2(const Cow& c1, const Cow& c2) { return c1.s < c2.s; }

int main()
{
	int n, w[N];
	Cow cow[N];
	
	while(scanf("%d", &n) != EOF) {
		int a, b, c; scanf("%d %d %d", &a, &b, &c);
		for(int i = 0; i < n; i++) cow[i].make(a, b, c);
		sort(cow, cow+n, cmp1);
		for(int i = 0; i < n; i++) { cow[i].wo = i; w[i] = cow[i].w; }
		sort(cow, cow+n, cmp2);
		int bn = 0;
		for(int i = 0; i < n; i++) {
			int cnt = 0, wn[N] = { 0 };
			for(int j = 0, k = 0; j < n; j++) {
				int mc = a*cow[i].h+b*w[j];
				for(; k < n && cow[k].s <= mc; k++)
					if(cow[k].legal(cow[i].h, w[j])) { cnt++; wn[cow[k].wo]++; }
				if(j != 0 && wn[j-1] != 0) cnt--;
				bn >?= cnt;
			}
		}
		printf("%d\n", bn);
	}

	return 0;
}