分数: 625 点
问题陈述
注意特殊的输入格式。
有 N 点 (X_i,Y_i) 在 xy- 平面。您会在输入中获得这些点。
另外, Q 整数对
给出了 (A_j,B_j) 。
定义 f(A_j,B_j) 作为索引的数量 i 满意 Y_i \ge A_j \times X_i + B_j.
查找 \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
约束
- 所有输入值均为整数。
- 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}
输入
输入由标准输入按以下格式给出:
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N Q G_0 R_a R_b
输出
将答案打印为整数。
示例输入 1
7 2 -2 -1 -2 0 1 2 1 -2 2 1 2 0 -1 10 1 5 5
示例输出 1
36
此输入包含十个问题。
生成的 (A_j,B_j) 是 (-2,4),(0,2),(-4,-2),(4,-5),(3,1),(-1,3),(2,-5),(3,-1),(3,5),(3,-2).