← 返回题目
题库练习 迷宫
← 上一题 下一题 →

A2821 | 迷宫

来源省选 / 2016
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

小雪和小可可被困在了一个无限大的迷宫中。

已经知道这个迷宫有 $N$ 堵环状的墙，如果把整个迷宫看作是一个二维平面，那么每一堵墙都是平面上一个圆。**任意两个圆不相交，不重合，也不会相切，但有可能相互包含**。小雪和小可可分别被困在了 $2$ 个不同的位置，且保证他们的位置与这些圆不重合。

他们只有破坏墙面才能穿过去。

小雪希望知道，如果他们要相见，至少要破坏掉多少堵墙？他们可以在任何位置相见。

输入格式

第一行有一个整数 $N$，表示有多少堵墙。

之后 $N$ 行，每一行有 $3$ 个整数 $x, y, r$，表示有一堵环状的墙是以 $(x,y)$ 为圆心，$r$ 为半径的。

再下一行有一个整数 $Q$，表示有多少组询问。

之后 $Q$ 行，每一行有 $4$ 个整数 $a, b, c, d$，给出了一组询问，表示小雪所在的位置为 $(a,b)$，小可可所在的位置为 $(c,d)$。

输出格式

输出 $Q$ 行，对应 $Q$ 次询问，每一行输出一个整数，表示最少需要破坏掉多少堵墙才能相见。

输入输出样例

输入 #1
3
0 0 1
3 0 1
2 0 4
1
0 0 3 0
输出 #1
2
输入 #2
3
0 0 1
0 0 2
4 0 1
2
0 0 4 0
0 0 0 4
输出 #2
3
2
C++ 编辑器
输入
输出