3307 - Beauty

8 
1 2 4 
5 1 
3 2 
2 3 
2 1 
7 2 
6 4 
5 1 
4 3

5

Hint

	第1，2，3，4，7号可以组成一支符合要求的队伍，没有更大的队伍了

Solution C++

/*
	author :hzoi_ztx
	title  :cogs 25482:Beauty
	ALG    :单调队列
	CMT    :枚举每个 H ,且使之为最小的 H , 再单调枚举 W ,
			则得到了当前的最小 H 与各个 W 值组合时的 ans

	[2014 10 27]
*/

#include <cstdio>
#include <algorithm>
#include <cstring>

#define  maxn  1005
#define  Size  1005

struct tx{
	int f , H , W , id ;
	bool operator < (const tx & b) const { return f < b.f ; }
} a[maxn] , b[maxn] ;

bool cmp(const tx a,const tx b) {
	if (a.W == b.W) return a.H < b.H;
	else return a.W < b.W ;
}
/*
struct monque{
	int q[Size] , head , rear ;
	int h ;
	int lim ;
	inline void clear()	{ head = 0 ; rear = -1 ; }
	inline bool empty()	{ return head > rear ; }
	inline int front()	{ return q[head] ; }
	inline int back()	{ return q[rear] ; }
	inline int cnt()    { return rear-head+1 ; }
	inline void pop_front() { head ++ ; }
	inline void pop_back()  { rear -- ; }
	inline void push_back(int x) { q[++head] = x ; } ;
	inline void push(int x) {
	}
} q ;*/

int n , A , B , C , ans = 0 ;
int h , w , v ;
int flag[maxn] ;

int main() {
//	#define READ
	#ifdef  READ
	    freopen("beauty.in" ,"r",stdin ) ;
	    freopen("beauty.out","w",stdout) ;
	#endif
	int i , j , k , now ;
	scanf("%d%d%d%d", &n , &A , &B , &C ) ;
	for (i = 1 ; i <= n ; i ++ ) {
		scanf("%d%d", &b[i].H , &b[i].W ) ;
	}
	std::sort(b+1 , b+n+1 , cmp) ;
	for (i = 1 ; i <= n ; i ++ ) {
		a[i] = b[i] ; a[i].id = i ;
		a[i].f = a[i].H*A+a[i].W*B-C ;
	}
	std::sort(a+1 , a+n+1) ;
	for (i = 1 ; i <= n ; i ++ ) {
		k = 1 ; now = 0 ;
		memset(flag , 0 , sizeof (flag)) ;
		for (j = 1 ; j <= n ; j ++ ) {
			v = b[i].H*A+b[j].W*B ;
			while (k<=n && a[k].f<=v) {
				if (a[k].H>=b[i].H && a[k].W>=b[j].W) {
					now ++ ; flag[a[k].id] ++ ;
				}
				k ++ ;
			}
			if (now > ans) ans = now ;
			now -= flag[j] ;
		}
	}
	printf("%d\n", ans ) ;
	#ifdef  READ
	    fclose(stdin ) ;
	    fclose(stdout) ;
	#else
	    getchar() ; getchar() ;
	#endif
	return 0 ;
}