AT_abc233_h [ABC233Ex] Manhattan Christmas Tree

题目描述

在二维平面上有 $N$ 棵圣诞树，第 $i$ 棵圣诞树位于坐标 $(x_i, y_i)$。

请回答以下 $Q$ 个查询。

查询 $i$：从点 $(a_i, b_i)$ 出发，按曼哈顿距离第 $K_i$ 近的圣诞树距离是多少？

输入格式

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

$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

输入 #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

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $0 \leq x_i \leq 10^5$
• $0 \leq y_i \leq 10^5$
• 若 $i \neq j$，则 $(x_i, y_i) \neq (x_j, y_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$
• 输入中的所有值均为整数

样例解释 1

从 $(3,5)$ 到第 $1,2,3,4$ 棵圣诞树的曼哈顿距离分别为 $2,2,5,1$。
因此，前 $4$ 个查询的答案分别为 $1,2,2,5$。

由 ChatGPT 4.1 翻译