[ABC244Ex] Linear Maximization

你有一个二元组集合 $S$ , 初始为空集. 有 $Q$ 次询问, 每次询问先把二元组 $(x_i,y_i)$ 加入集合 $S$ , 再回答 $\max\limits_{(x,y)\in S}\{a_ix+b_iy\}$ .

[problemUrl]: https://atcoder.jp/contests/abc244/tasks/abc244_h $ 2 $ 次元平面上の点の集合 $ 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_ix\ +\ B_iy\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 $ 個目のクエリに対する答えを出力せよ。

4
1 0 -1 -1
0 1 2 0
-1 0 1 1
0 -1 1 -2

-1
2
1
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

0
35
31
21
36
87
0
36
31

### 制約 - 入力は全て整数 - $ 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) $ ### Sample Explanation 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 $ となり、これが最大値を取ります。