[AHOI2016初中组] 迷宫
题目描述
小雪和小可可被困在了一个无限大的迷宫中。
已经知道这个迷宫有 $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
说明
对于 $20\%$ 的数据,$0\le N\le 200$。
对于 $40\%$ 的数据,$0\le N\le 1000$。
对于 $100\%$ 的数据,$0\le N, Q\le 8000,-10^8\le x,y,r, a, b, c, d\le 10^8$。
此外,还有额外的 $20\%$ 的数据,满足 $0\le N\le 1000,0\le Q\le 1000$。
大数据点时限 $\rm 3\ s$。