102447: [AtCoder]ABC244 Ex - Linear Maximization
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $600$ points
Problem Statement
There is a set $S$ of points on a two-dimensional plane. $S$ is initially empty.
For each $i = 1, 2, \dots, Q$ in this order, process the following query.
- You are given integers $X_i, Y_i, A_i$, and $B_i$. Add point $(X_i, Y_i)$ to $S$, and then find $\displaystyle \max_{(x,y) \in S}\left\{A_ix + B_iy\right\}$.
Constraints
- All values in input are integers.
- $1≤Q≤2 \times 10^5$
- $|X_i|, |Y_i|, |A_i|, |B_i| ≤10^9$
- If $i ≠ j$, then $(X_i, Y_i) ≠ (X_j, Y_j)$.
Input
Input is given from Standard Input in the following format:
$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$
Output
Print $Q$ lines. The $i$-th line should contain the answer for the $i$-th query.
Sample Input 1
4 1 0 -1 -1 0 1 2 0 -1 0 1 1 0 -1 1 -2
Sample Output 1
-1 2 1 2
- When $i = 1$: add point $(1, 0)$ to $S$, then it will become $S = \{(1, 0)\}$. For $(x, y) = (1, 0)$, we have $-x - y = -1$, which is the maximum.
- When $i = 2$: add point $(0, 1)$ to $S$, then it will become $S = \{(0, 1), (1, 0)\}$. For $(x, y) = (1, 0)$, we have $2x = 2$, which is the maximum.
- When $i = 3$: add point $(-1, 0)$ to $S$, then it will become $S = \{(-1, 0), (0, 1), (1, 0)\}$. For $(x, y) = (1, 0)$ or $(x, y) = (0, 1)$, we have $x + y = 1$, which is the maximum.
- When $i = 4$: add point $(0, -1)$ to $S$, then it will become $S = \{(-1, 0), (0, -1), (0, 1), (1, 0)\}$. For $(x, y) = (0, -1)$, we have $x - 2y = 2$, which is the maximum.
Sample Input 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
Sample Output 2
0 35 31 21 36 87 0 36 31
Input
题意翻译
你有一个二元组集合 $S$ , 初始为空集. 有 $Q$ 次询问, 每次询问先把二元组 $(x_i,y_i)$ 加入集合 $S$ , 再回答 $\max\limits_{(x,y)\in S}\{a_ix+b_iy\}$ .Output
得分：600分
部分
问题描述
二维平面上有一个点集S。S最初是空的。
按顺序处理以下每个查询。
给出整数$X_i$，$Y_i$，$A_i$和$B_i$。将点$(X_i, Y_i)$添加到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$
如果$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)$添加到$S$，则变为$S = \{(1, 0)\}$。对于$(x, y) = (1, 0)$，我们有$-x - y = -1$，这是最大值。
- 当$i = 2$：将点$(0, 1)$添加到$S$，则变为$S = \{(0, 1), (1, 0)\}$。对于$(x, y) = (1, 0)$，我们有$2x = 2$，这是最大值。
- 当$i = 3$：将点$(-1, 0)$添加到$S$，则变为$S = \{(-1, 0), (0, 1), (1, 0)\}$。对于$(x, y) = (1, 0)$或$(x, y) = (0, 1)$，我们有$x + y = 1$，这是最大值。
- 当$i = 4$：将点$(0, -1)$添加到$S$，则变为$S = \{(-1, 0), (0, -1), (0, 1), (1, 0)\}$。对于$(x, y) = (0, -1)$，我们有$x - 2y = 2$，这是最大值。