← 返回题目列表

AtCoder · code_festival_final_i

I. 形状

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

問題文

在二维平面上, (x_i,y_i) 到 r_i 的曼哈顿距离恰好为的点的集合组成的图形有 n 个。 无论哪 2 个图形,它们构成的点集合都没有公共部分。

此时,回答“从坐标 (x1,y1) 移动到坐标 (x2,y2) 时必须经过的最少点数”的查询 m 个,请依次回答。 由查询给出 2 个坐标保证不包含在任何图形的点集中。

移动时,可以移动相似的实数坐标。


入力

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

n
x_1 y_1  r_1
x_2 y_2 r_2
:
x_n y_n r_n
m
x1_1 y1_1 x2_1 y2_1
x1_2 y1_2 x2_2 y2_2
:
x1_m y1_m x2_m y2_m
  • 1 行表示图形数量的整数 n (1 ≦ n ≦ 10^5) 。
  • 1 从行 n 行表示每个图形的信息 3 整数 x_i,y_i,r_i (-10^8 ≦ x_i,y_i ≦ 10^8, 1 ≦ r_i ≦ 10^8) 给出。任意两个图形所构成的点集没有交集。
  • n+1 行表示查询的数量整数 m (1 ≦ m ≦ 10^5) 。
  • n+2 从行 m 行表示每个查询的两个信息 4 整数 x1_i,y1_i,x2_i,y2_i (-10^8 ≦ x1_i,y1_i,x2_i,y2_i ≦ 10^8) 给出。这两个坐标保证不包含在任何图形的点集中。

出力

从第1行开始 m 按照给定顺序以换行符分隔输出各库里里的答案。最后一行也要换行。


入力例1

5
0 0 1
0 0 5
0 0 9
0 0 13
20 20 1
4
0 0 13 13
0 0 0 7
0 2 0 3
0 0 20 20

出力例1

4
2
0
5

表示输入输出示例1的图如下。


入力例2

6
0 0 10
0 5 4
5 0 4
0 -5 4
-5 0 4
8 8 2
4
0 5 0 -5
6 0 10 10
-5 0 0 0
5 0 8 8

出力例2

2
2
1
3

表示输入输出示例2的图如下。