分数: 600 点
问题陈述
有一套 二维平面上的点的 S 。 S 最初是空的。
对于每个 i = 1, 2, \dots, Q 按照此顺序,处理以下查询。
- 给你整数 X_i, Y_i, A_i,和 B_i。 添加点 (X_i, Y_i) to S,然后找到 \displaystyle \max_{(x,y) \in S}\left\{A_ix + B_iy\right\}.
约束
- 输入中的所有值都是整数。
- 1≤Q≤2 \times 10^5
- |X_i|, |Y_i|, |A_i|, |B_i| ≤10^9
- If i ≠ j,然后 (X_i, Y_i) ≠ (X_j, Y_j).
输入
输入由标准输入按以下格式给出:
Q X_1 Y_1 A_1 B_1 X_2 Y_2 A_2 B_2 \vdots X_Q Y_Q A_Q B_Q
输出
打印 Q 行。 的 i- 第行应包含以下问题的答案 i第一个查询。
示例输入 1
4 1 0 -1 -1 0 1 2 0 -1 0 1 1 0 -1 1 -2
示例输出 1
-1 2 1 2
- 当 i = 1: 添加点 (1, 0) to S,那么它就会变成 S = \{(1, 0)\}。 对于 (x, y) = (1, 0),我们有 -x - y = -1,这是最大值。
- 当 i = 2: 添加点 (0, 1) to S,那么它就会变成 S = \{(0, 1), (1, 0)\}。 对于 (x, y) = (1, 0),我们有 2x = 2,这是最大值。
- 当 i = 3: 添加点 (-1, 0) to S,那么它就会变成 S = \{(-1, 0), (0, 1), (1, 0)\}。 对于 (x, y) = (1, 0) or (x, y) = (0, 1),我们有 x + y = 1,这是最大值。
- 当 i = 4: 添加点 (0, -1) to S,那么它就会变成 S = \{(-1, 0), (0, -1), (0, 1), (1, 0)\}。 对于 (x, y) = (0, -1),我们有 x - 2y = 2,这是最大值。
示例输入 2
9 -1 4 -8 -2 9 -9 -7 7 4 1 6 7 -4 -1 -4 -5 -9 3 -2 -6 -1 0 -8 5 -8 -5 0 0 8 3 0 -4 2 -5 2 5
示例输出 2
0 35 31 21 36 87 0 36 31