AT_abc344_g [ABC344G] Points and Comparison

题目描述

请注意特殊的输入格式。

在 $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_{j=1}^Q f(A_j, B_j)$。

但是，由于本题中的 $Q$ 非常大，$(A_j, B_j)$ 不会直接给出。
取而代之，给出 $G_0, R_a, R_b$，$(A_j, B_j)$ 按如下方式生成：

• 首先，对于 $n \ge 0$，定义 $G_{n+1} = (48271 \times G_n) \bmod (2^{31}-1)$。
• 对于 $j=1,2,\dots,Q$，$(A_j, B_j)$ 按如下方式生成：
  • $A_j = -R_a + (G_{3j-2} \bmod (2 \times R_a + 1))$
  • $B_j = -R_b + ((G_{3j-1} \times (2^{31}-1) + G_{3j}) \bmod (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$

输入格式

输入以如下格式从标准输入读入：

$N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\cdots$ $X_N$ $Y_N$ $Q$ $G_0$ $R_a$ $R_b$

输出格式

请输出答案的整数值。

输入输出样例 #1

输入 #1

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

输出 #1

36

说明/提示

数据范围

• 所有输入均为整数。
• $1 \le N \le 5000$
• $1 \le Q \le 10^7$
• $|X_i|, |Y_i| \le 10^8$
• $(X_i, Y_i)$ 互不相同。
• $0 \le G_0 < 2^{31}-1$
• $0 \le R_a \le 10^8$
• $0 \le R_b \le 10^{16}$

样例解释 1

该输入包含 $10$ 个询问。生成的 $(A_j, B_j)$ 分别为 $(-2,4), (0,2), (-4,-2), (4,-5), (3,1), (-1,3), (2,-5), (3,-1), (3,5), (3,-2)$。

由 ChatGPT 4.1 翻译