UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4434. [Cerc2015]Ice Igloos

Statistics 下载数据

Description

一个坐落在北极冰冻湖面上的渔村因全球变暖而面临危险——湖面开始破碎。村庄内有n座球形冰屋,每座冰屋在湖面上占据了一块圆形区域。
一座冰屋可以视为平面座标系中的一个圆:其圆心座标为整数,其半径为小于1的一位浮点数。给出冰面断裂的座标,这些村民希望知道每次断裂会有多少个冰屋受到影响。
形式上,给出q个询问,每个询问包括一条由两个端点确定的线段,查询每条线段贯穿的冰屋数。如果线段与圆的内部有至少一个交点,则线段贯穿了这座冰屋。

Input

第一行包括一个整数n(1<=n<=100 000)——冰屋数。
接下来的n行每行包括三个数x,y和r——冰屋的座标和半径。x和y为整数且1<=x,y<=500。r是一位浮点数且0<r<1。冰屋之间不存在重叠或接触。
你可以认为,对于任一冰屋i和线段s 的距离的平方小于r2-10-5或大于r2+10-5。

Output

输出包括q行。第k行包括一个整数——被第k条线段穿过的冰屋数

Sample Input

5
4 2 0.6
7 3 0.7
8 5 0.8
1 3 0.7
3 4 0.4
2
3 1 9 6
3 4 7 2

Sample Output

2
1

Hint

Source