Ex - Manhattan Christmas Tree Editorial /

Time Limit: 7 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

2 次元平面上にクリスマスツリーが 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 です。
よって、最初の 4 つのクエリの答えはそれぞれ 1,2,2,5 です。

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.