← 返回题目列表

AtCoder · typical90_aj

036. 最大曼哈顿距离(★5)

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

配点: 5 点

問題文

在二维坐标平面上有不同的 N 点 P_1, P_2, \ldots, P_N ,并且给定点 P_i 的坐标是 (x_i, y_i) 。

下面 Q 查询。

  • i (1 \leq i \leq Q) 个查询中,整数 q_i ,所以点 P_{q_i} 和 按字典顺序比较 N 输出点与点之间的曼哈顿距离的最大值。
  • 也就是说,点 P_s 和点 P_t 的曼哈顿距离是 \rm{dist}(P_s, P_t) 时,\rm{max}(\rm{dist}(P_{q_i}, P_1), \cdots, \rm{dist}(P_{q_i}, P_N)) 的值。
关于曼哈顿距离的座標 (x_1, y_1) 和坐标 (x_2, y_2) 之间的曼哈顿距离,|x_1 - x_2| + |y_1 - y_2| 中定义。

制約

  • 2 \leq N \leq 100000
  • 1 \leq Q \leq N
  • -10^9 \leq x_i, y_i \leq 10^9
  • (x_i, y_i) \neq (x_j, y_j) (1 \leq i < j \leq N)
  • 1 \leq q_i \leq N (1 \leq i \leq Q)
  • q_i \neq q_j (1 \leq i < j \leq Q)
  • 给出的所有输入均为整数

入力

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

N Q 
x_1 y_1
\vdots
x_N y_N
q_1
\vdots
q_Q

出力

给定的 Q 个查询的答案用换行分隔。 1 请按行输出。


入力例 1

3 3
-1 2
1 1
-2 -3
1
2
3

出力例 1

6
7
7

1 第几个查询关注点 1 。

  • 点 1 和点 1 的曼哈顿距离是 |-1 - (-1)| + |2 - 2| = 0
  • 点 1 和点 2 的曼哈顿距离是 |-1 - 1| + |2 - 1| = 3
  • 点 1 和点 3 的曼哈顿距离是 |-1 - (-2)| + |2 - (-3)| = 6

因此,1 第几个查询中,这些曼哈顿距离的最大值是 6 。


入力例 2

5 3
-2 -2
-1 -1
0 0
1 1
2 2
5
3
1

出力例 2

8
4
8

入力例 3

2 1
-1000000000 -1000000000
1000000000 1000000000
1

出力例 3

4000000000

小心溢出。