AT_pakencamp_2024_day3_1_f RGB Triangle

在二维平面上有 $R$ 个红点，$G$ 个绿点，$B$ 个蓝点。 第 $i$ 个红点的坐标为 $(RX_i, RY_i)$。 第 $i$ 个绿点的坐标为 $(GX_i, GY_i)$。 第 $i$ 个蓝点的坐标为 $(BX_i, BY_i)$。 可能有多个点重合在同一坐标上。 定义函数 $\text{dist}, \text{tri}$ 如下： - $\text{dist}((x_1,y_1),(x_2,y_2)) = |x_1 - x_2| + |y_1 - y_2|$ - $\text{tri}(r, g, b) = \text{dist}((RX_r, RY_r), (GX_g, GY_g)) + \text{dist}((GX_g, GY_g), (BX_b, BY_b)) + \text{dist}((BX_b, BY_b), (RX_r, RY_r))$ 请处理 $Q$ 个询问。第 $i$ 个询问给出整数三元组 $(x_i, y_i, z_i)$，请你求出满足以下条件的 $(s, t, u)$ 的 $\text{tri}(s, t, u)$ 的最大值： - 如果 $x_i = -1$，则 $1 \leq s \leq R$，否则 $s = x_i$； - 如果 $y_i = -1$，则 $1 \leq t \leq G$，否则 $t = y_i$； - 如果 $z_i = -1$，则 $1 \leq u \leq B$，否则 $u = z_i$。

输入从标准输入中读入，格式如下： > $R$ $G$ $B$ > $RX_1$ $RY_1$ > $RX_2$ $RY_2$ > $\vdots$ > $RX_R$ $RY_R$ > $GX_1$ $GY_1$ > $GX_2$ $GY_2$ > $\vdots$ > $GX_G$ $GY_G$ > $BX_1$ $BY_1$ > $BX_2$ $BY_2$ > $\vdots$ > $BX_B$ $BY_B$ > $Q$ > $x_1$ $y_1$ $z_1$ > $x_2$ $y_2$ $z_2$ > $\vdots$ > $x_Q$ $y_Q$ $z_Q$

输出 $Q$ 行。 第 $i$ 行输出第 $i$ 个询问的答案。

### 样例解释 1 - 关于第 $2$ 个询问，$\text{tri}(1,1,2)$ 最大。 - 关于第 $3$ 个询问，$\text{tri}(3,2,1)$ 最大。 - 关于第 $4$ 个询问，$\text{tri}(2,2,1)$ 最大。 - 关于第 $5$ 个询问，$\text{tri}(2,2,1)$ 最大。 ### 数据范围 - $1 \leq R, G, B$ - $R+G+B \leq 200000$ - $0 \leq RX_i, RY_i, GX_i, GY_i, BX_i, BY_i \leq 10^9$ - $1 \leq Q \leq 200000$ - $1 \leq x_i \leq R$ 或 $x_i=-1$ - $1 \leq y_i \leq G$ 或 $y_i=-1$ - $1 \leq z_i \leq B$ 或 $z_i=-1$ - 输入均为整数。 由 ChatGPT 5 翻译