P4354 [CERC2015] Ice Igloos

2015 年中欧区域竞赛第一题

给你 $n$ 个圆，$m$ 条线段，请你求出每条线段与多少圆相交。

第一行一个整数 $n$ 表示圆的个数； 接下来 $n$ 行每行两个整数 $x,y$ 和一个实数 $r$ 表示圆心坐标和半径； 第 $n+2$ 行一个整数 $m$ 表示线段个数； 接下来 $m$ 行每行四个整数 $x1,y1,x2,y2$，表示线段的两个端点 $(x1,y1),(x2,y2)$。

总共 $m$ 行，每行一个整数，表示该条线段和多少圆相交。 感谢 @Kelin 提供的翻译。

 对于 $100\%$ 的数据，$n,m \le 10^5,1 \le x_i,y_i \le 500,0 \lt r_i \lt 1$。