Score: $625$ points

问题描述

请注意特殊的输入格式。

在 $xy$ 平面上有 $N$ 个点 $(X_i, Y_i)$，这些点在输入中给出。

同时，给出了 $Q$ 对整数 $(A_j, B_j)$。
定义 $f(A_j, B_j)$ 为满足 $Y_i \ge A_j \times X_i + B_j$ 的索引 $i$ 的数量。

求 $\displaystyle \sum^{Q}_{j=1} f(A_j,B_j)$。

此处，$Q$ 可能非常大，因此不直接给出 $(A_j, B_j)$。
而是给出 $G_0$、$R_a$ 和 $R_b$，并通过以下方式生成 $(A_j, B_j)$：

• 首先，对于 $n \geq 0$，定义 $G_{n+1} = (48271 \times G_n) \mod (2^{31}-1)$。
• 对于 $j=1,2,\dots,Q$，按以下方式生成 $(A_j, B_j)$：
  • $A_j = -R_a + (G_{3j - 2} \mod (2 \times R_a + 1) )$
  • $B_j = -R_b + ((G_{3j - 1} \times (2^{31}-1) + G_{3 j}) \mod (2 \times R_b + 1) )$

通过这种方法可以证明，$A_j$ 和 $B_j$ 满足以下约束条件：

• $-R_a \le A_j \le R_a$
• $-R_b \le B_j \le R_b$

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Pay attention to the special input format.

There are $N$ points $(X_i,Y_i)$ in the $xy$-plane. You are given these points in the input.

Also, $Q$ pairs of integers $(A_j,B_j)$ are given.
Define $f(A_j,B_j)$ as the number of indices $i$ satisfying $Y_i \ge A_j \times X_i + B_j$.

Find $\displaystyle \sum^{Q}_{j=1} f(A_j,B_j)$.

Here, $Q$ gets very large, so $(A_j,B_j)$ are not given directly.
Instead, $G_0$, $R_a$, and $R_b$ are given, and $(A_j,B_j)$ are generated as follows:

• First, for $n \ge 0$, define $G_{n+1} = (48271 \times G_n) \mod (2^{31}-1)$.
• For $j=1,2,\dots,Q$, generate $(A_j,B_j)$ as follows:
  • $A_j = -R_a + (G_{3j - 2} \mod (2 \times R_a + 1) )$
  • $B_j = -R_b + ((G_{3j - 1} \times (2^{31}-1) + G_{3 j}) \mod (2 \times R_b + 1) )$

From this method, it can be shown that $A_j$ and $B_j$ satisfy the following constraints:

• $-R_a \le A_j \le R_a$
• $-R_b \le B_j \le R_b$

Constraints

• All input values are integers.
• $1 \le N \le 5000$
• $1 \le Q \le 10^7$
• $|X_i|, |Y_i| \le 10^8$
• The pairs $(X_i,Y_i)$ are distinct.
• $0 \le G_0 < (2^{31}-1)$
• $0 \le R_a \le 10^8$
• $0 \le R_b \le 10^{16}$

Input

The input is given from Standard Input in the following format:

$N$

$X_1$ $Y_1$

$X_2$ $Y_2$

$\vdots$

$X_N$ $Y_N$

$Q$

$G_0$ $R_a$ $R_b$

Output

Print the answer as an integer.

Sample Input 1

7
2 -2
-1 -2
0 1
2 1
-2 2
1 2
0 -1
10
1 5 5

Sample Output 1

36

This input contains ten questions.
The generated $(A_j,B_j)$ are $(-2,4),(0,2),(-4,-2),(4,-5),(3,1),(-1,3),(2,-5),(3,-1),(3,5),(3,-2)$.