分数: 600 点
问题陈述
有 N 二维平面中的圣诞树。的 i- 第棵树位于坐标处 (x_i,y_i).
回答以下问题 Q 查询。
查询 i: 之间的距离是多少 (a_i,b_i) 和 K_i-距离该点最近的圣诞树,以曼哈顿距离测量?
约束
- 1\leq N \leq 10^5
- 0\leq x_i\leq 10^5
- 0\leq y_i\leq 10^5
- (x_i,y_i) \neq (x_j,y_j) if i\neq j.
- 1\leq Q \leq 10^5
- 0\leq a_i\leq 10^5
- 0\leq b_i\leq 10^5
- 1\leq K_i\leq N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N x_1 y_1 \vdots x_N y_N Q a_1 b_1 K_1 \vdots a_Q b_Q K_Q
输出
打印 Q 行。
的 i- 第行应包含查询的答案 i.
示例输入 1
4 3 3 4 6 7 4 2 5 6 3 5 1 3 5 2 3 5 3 3 5 4 100 200 3 300 200 1
示例输出 1
1 2 2 5 293 489
距离 (3,5) 到 1-st, 2-nd, 3-rd, 4到该点的树是 2, 2, 5, 1。
因此,前四个查询的答案是 1, 2, 2, 5。