背景

2015 年中欧区域竞赛第一题

题目描述

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

输入格式

第一行一个整数 $n$ 表示圆的个数；

接下来 $n$ 行每行两个整数 $x,y$ 和一个实数 $r$ 表示圆心坐标和半径；

第 $n+2$ 行一个整数 $m$ 表示线段个数；

接下来 $m$ 行每行四个整数 $x1,y1,x2,y2$，表示线段的两个端点 $(x1,y1),(x2,y2)$。

输出格式

总共 $m$ 行，每行一个整数，表示该条线段和多少圆相交。

感谢 @Kelin 提供的翻译。

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

提示

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