P4354 [CERC2015] Ice Igloos

题目描述

给你$n$个圆$,m$条线段$,$求每条线段与多少圆相交

$n,m\le10^5,1\le x_i,y_i\le500,0\lt r_i\lt 1$

输入格式

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

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

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

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

输出格式

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

感谢@Kelin 提供的翻译

输入输出样例 #1

输入 #1

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

输出 #1

2
1