← 返回题目列表

AtCoder · pakencamp_2024_day3_1_f

F. RGB 三角形

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

配点 : 100 点

問題文

在二维平面上 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 、x_i\neq -1 如果 打印第 s=x_i
    • y_i=-1 如果 打印第 1\leq t\leq G 、y_i\neq -1 如果 打印第 t=y_i
    • z_i=-1 如果 打印第 1\leq u\leq B 、z_i\neq -1 如果 打印第 u=z_i

制約

  • 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
  • 输入全部为整数

入力

输入是按以下格式从标准输入给出的。

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

4 2 2
2 0
2 5
0 4
0 1
1 3
0 0
1 7
0 0
7
1 2 2
1 -1 2
3 -1 -1
-1 -1 -1
-1 2 -1
-1 2 2
4 2 2

出力例 1

4
10
16
18
18
14
2
  • 2 个查询,\text{tri}(1,1,2) 是最大值。
  • 3 个查询,\text{tri}(3,2,1) 是最大值。
  • 4 个查询,\text{tri}(2,2,1) 是最大值。
  • 5 个查询,\text{tri}(2,2,1) 是最大值。