AT_abc244_h [ABC244Ex] Linear Maximization

在二维平面上有一个点集 $S$，初始时 $S$ 为空。 请依次处理 $i = 1, 2, \dots, Q$ 的以下查询： - 给定整数 $X_i, Y_i, A_i, B_i$。在 $S$ 中加入点 $(X_i, Y_i)$ 后，求 $\displaystyle\max_{(x, y) \in S} \left\{A_i x + B_i y\right\}$ 的值。

输入以如下格式从标准输入给出。 > $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 \leq Q \leq 2 \times 10^5$ - $|X_i|, |Y_i|, |A_i|, |B_i| \leq 10^9$ - 若 $i \neq j$，则 $(X_i, Y_i) \neq (X_j, Y_j)$。 ## 样例解释 1 - 当 $i = 1$ 时：向 $S$ 中加入点 $(1, 0)$，此时 $S = \{(1, 0)\}$。当 $(x, y) = (1, 0)$ 时，$-x - y = -1$，这是最大值。 - 当 $i = 2$ 时：向 $S$ 中加入点 $(0, 1)$，此时 $S = \{(0, 1), (1, 0)\}$。当 $(x, y) = (1, 0)$ 时，$2x = 2$，这是最大值。 - 当 $i = 3$ 时：向 $S$ 中加入点 $(-1, 0)$，此时 $S = \{(-1, 0), (0, 1), (1, 0)\}$。当 $(x, y) = (1, 0)$ 或 $(x, y) = (0, 1)$ 时，$x + y = 1$，这是最大值。 - 当 $i = 4$ 时：向 $S$ 中加入点 $(0, -1)$，此时 $S = \{(-1, 0), (0, -1), (0, 1), (1, 0)\}$。当 $(x, y) = (0, -1)$ 时，$x - 2y = 2$，这是最大值。 由 ChatGPT 4.1 翻译