← 返回题目列表

AtCoder · abc233_h

Ex. 曼哈顿圣诞树

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

分数: 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。