Description

NBA 每年都有球员选秀环节. 通常用速度和身高两项数据来衡量一个篮球运动员的基本素质. 假如一支球队里速度最慢的球员速度为 \(minV\), 身高最矮的球员高度为 \(minH\), 那么这支 球队的所有队员都应该满足:\(a \times (height - minH) + b \times (speed - minV) \leq 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

Data Range

对于所有数据, 满足:\(n \leq 5000, height, speed \leq 10000, a, b, c \leq 2^{31}-1\)

Explanation

在一定的范围内如果将他们的权值排序会发现其实是具有单调性的. 所以说, 虽然转移的时间复杂度是每次 \(O(n^2)\) 的, 但是我们可以保证均摊是 \(O(n^2)\) 的.

这样一来, 只需要暴力枚举速度下限和身高下限就可以了, 余下的在已经排序的数组上瞎搞 一发就可以解决问题了 (减号写成加号 WA 不停是什么情况)

Source Code

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 5010;

struct player {
    int hei, vel, sum;
} arr[2][maxn];

bool cmp_hei(player a, player b)
    { return a.hei < b.hei; }
bool cmp_sum(player a, player b)
    { return a.sum < b.sum; }
bool check(int __x, int __y, int minn, int maxx)
    { return arr[__x][__y].vel >= minn
        && arr[__x][__y].vel <= maxx; }

int n, A, B, C;

int main(int argc, char** argv)
{
    scanf("%d%d%d%d", &n, &A, &B, &C);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &arr[0][i].hei,
            &arr[0][i].vel);
        arr[0][i].sum = A * arr[0][i].hei
            + B * arr[0][i].vel;
        arr[1][i] = arr[0][i];
    }
    sort(arr[0] + 1, arr[0] + 1 + n, cmp_hei);
    sort(arr[1] + 1, arr[1] + 1 + n, cmp_sum);
    // Enumerate the velocity of team members
    int res = 0;
    for (int i = 1; i <= n; i++) {
        int minn = arr[0][i].vel,
            maxx = minn + C / B;
        int l = 0, r = 0, t_res = 0;
        // Enumerate the height of team members
        for (int j = 1; j <= n; j++) {
            int hei = arr[0][j].hei,
                vel = arr[0][i].vel;
            while (r < n && arr[1][r + 1].sum - A * hei - B * vel <= C)
                t_res += check(1, ++r, minn, maxx);
            while (l < n && arr[0][l + 1].hei < hei)
                t_res -= check(0, ++l, minn, maxx);
            // Update final result
            res = max(res, t_res);
        }
    }
    printf("%d\n", res);
    return 0;
}