A22532.迷宫
普及/提高-
省选
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小雪和小可可被困在了一个无限大的迷宫中。
已经知道这个迷宫有 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
说明/提示
0≤N≤1000。