102337: [AtCoder]ABC233 Ex - Manhattan Christmas Tree

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

There are $N$ Christmas trees in the two-dimensional plane. The $i$-th tree is at coordinates $(x_i,y_i)$.

Answer the following $Q$ queries.

Query $i$: What is the distance between $(a_i,b_i)$ and the $K_i$-th nearest Christmas tree to that point, measured in Manhattan distance?

Constraints

  • $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$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$x_1$ $y_1$
$\vdots$
$x_N$ $y_N$
$Q$
$a_1$ $b_1$ $K_1$
$\vdots$
$a_Q$ $b_Q$ $K_Q$

Output

Print $Q$ lines.
The $i$-th line should contain the answer to Query $i$.


Sample Input 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

Sample Output 1

1
2
2
5
293
489

The distances from $(3,5)$ to the $1$-st, $2$-nd, $3$-rd, $4$-th trees to that point are $2$, $2$, $5$, $1$, respectively.
Thus, the answers to the first four queries are $1$, $2$, $2$, $5$, respectively.

Input

题意翻译

在平面直角坐标系中有 $N$ 个点,第 $i$ 个点的编号是 $x_i,y_i$。 有 $Q$ 个询问,每个询问给你一个坐标 $a_i,b_i$ 和一个整数 $k_i$,求距离 $a_i,b_i$ 第 $k_i$ 近的点与 $a_i,b_i$ 的距离。 上述的距离指的均是曼哈顿距离。 + $1 \le N \le 10^5$,$1 \le Q \le 10^5$ + $0 \le x_i \le 10^5$,$0 \le y_i \le 10^5$,$1 \le k_i \le N$ + 对于任意两个互不相同的 $i$ 和 $j$,保证 $(x_i,y_i) \neq (x_j,y_j)$ Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)

Output

分数: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$
  • 如果$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$
  • 输入中的所有值都是整数。

输入

输入将以以下格式从标准输入给出:

$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$、$2$、$3$、$4$棵树的距离分别为$2$、$2$、$5$、$1$。
因此,前四个查询的答案分别为$1$、$2$、$2$、$5$。

加入题单

上一题 下一题 算法标签: