NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem62--迷宫 [maze]

62: 迷宫 [maze]

Time Limit: 1000 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

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

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

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

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

Input

第一行有一个整数 N,表示有多少堵墙,保证 0<=N<=8000。

之后 N 行,每一行有三个整数 x,y 和 r,表示有一堵环状的墙是以(x,y)为圆形,r为半径的。保证-100000000<=x,y,r<=100000000。

再下一行有一个整数 Q,表示有多少组询问,保证 1<=Q<=8000。

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

Output

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

Sample Input Copy

3
0 0 1
3 0 1
2 0 4
1
0 0 3 0

Sample Output Copy

2

HINT

数据规模:

对于 20%的数据,0<=N<=200。

对于 40%的数据,0<=N<=1000。

对于 100%的数据,0<=N<=8000,0<=Q<=8000。

此外,还有额外的 20%的数据,满足 0<=N<=1000,0<=Q<=1000。

所有数绝对值不超过 100000000。

Source/Category