Description
NBA每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为(minV)，身高最矮的球员高度为(minH)，那么这支球队的所有队员都应该满足: (A cdot ( height – minH ) + B cdot ( speed – minV ) leqslant C) 其中(A)和(B)，(C)为给定的经验值。这个式子很容易理解，如果一个球队的球员速度和身高差距太大，会造成配合的不协调。 请问作为球队管理层的你，在(N)名选秀球员中，最多能有多少名符合条件的候选球员。
Input
第一行四个数(N)、(A)、(B)、(C) 下接(N)行每行两个数描述一个球员的(height)和(speed)
Output
最多候选球员数目。
Sample Input
4 1 2 10
5 1
3 2
2 3
2 1
Sample Output
4
HINT
数据范围： (N leqslant 5000) ,(heigh)t和(speed)不大于(10000)。(A)、(B)、(C)在长整型以内。
Solution
尺取好题。首先不等式原式很烦人，我们要试着转一下。移项得(A cdot height + B cdot speed leqslant A cdot minH + B cdot minV + C)。
设(s = A cdot height + B cdot speed)。
暴力容易做，枚举(minV)和(minH)，看有多少个球员能加入。
考虑先枚举一维，枚举(minV)，忽略所有(speed)小于(minV)的球员。
下面枚举(minH)。如果将球员按(height)排序，(A cdot height + B cdot speed)并不单调，所以无法直接尺取。然而(A cdot minH + B cdot minV + C)是单调的，这个性质就是解题关键。我们维护两个序列，第一个序列按照(s)从小到大排序，第二个序列按照 (height) 从小到大排序，我们从小到大枚举(minH)。然后就可以尺取了。
尺取维护两个指针，(r)表示第一个序列中([1, r))满足不等式的限制，(l)表示第二个序列中([1, l))满足(minH)的限制。
大概内容已经说完了，剩下的就看代码吧。
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, flag = 1; char ch = getchar();
while (ch > '9' || ch < '0') { if (ch == '-') flag = -1; ch = getchar(); }
while (ch <= '9' && ch >= '0') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * flag;
}
inline void write(int x) { if (x >= 10) write(x / 10); putchar(x % 10 + '0'); }
#define N 5001
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define ll long long
int n;
ll A, B, C;
struct manType { int h, v; ll s; void get() { s = A * h + B * v; } }x[3][N];
bool cmpH(const manType a, const manType b) { return a.h < b.h; }
bool cmpS(const manType a, const manType b) { return a.s < b.s; }
int main() {
n = read(), A = read(), B = read(), C = read();
rep(i, 1, n) x[0][i].h = read(), x[0][i].v = read(), x[0][i].get(), x[1][i] = x[0][i];
sort(x[0] + 1, x[0] + 1 + n, cmpS), sort(x[1] + 1, x[1] + 1 + n, cmpH);
int ans = 0;
rep(i, 1, n) {
int l = 1, r = 1, cnt = 0;
rep(j, 1, n) {
int minV = x[0][i].v, minH = x[1][j].h;
ll val = minH * A + minV * B + C;
while (r <= n && x[0][r].s <= val)
cnt += x[0][r].v >= minV && x[0][r].h >= x[1][l].h, r++;
//如果x[0][r] < x[1][l],那么它在上一轮就会被删除
while (l <= n && x[1][l].h < minH)
cnt -= x[1][l].s <= val && x[1][l].v >= minV, l++;
ans = max(ans, cnt);
}
}
write(ans);
return 0;
}