[Cerc2015]Ice Igloos

题目描述

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

---

输入格式

第一行包括一个整数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。

---

输出格式

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

---

样例输入

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

---

样例输出

2
1

---

提示

没有写明提示

---

题目来源

没有写明来源