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^{Q}_{j=1} 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) \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$

输入格式

输入从标准输入按如下格式给出： $N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$ $Q$ $G_0$ $R_a$ $R_b$

输出格式

输出一个整数，表示答案。

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

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}$该输入包含十个查询。
生成的 $(A_j,B_j)$ 为 $(-2,4),(0,2),(-4,-2),(4,-5),(3,1),(-1,3),(2,-5),(3,-1),(3,5),(3,-2)$。

标签: AtCoder|abc344G

来源

AtCoder|abc344G