← 返回题目列表

AtCoder · abc244_h

Ex. 线性最大化

中文机器翻译题面 查看原题

分数: 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