#P18612. Epidemic Escape

Epidemic Escape

Epidemic Escape

二维平面的原点停着一艘飞船,平面内还有 n 个感染点。在时刻 t=0,每个感染点同时开始传播感染:在时刻 t,该点的感染区域是以它为圆心、半径为 t 的圆盘,边界也包含在内。

飞船也从时刻 t=0 开始,以速度 1 沿选定方向一直作直线运动。飞船拥有一个护盾等级。当同时包含飞船的感染圆盘数量达到或超过护盾等级时,飞船立即被摧毁。

船长要独立考虑 q 种航行方案。第 j 种方案给出方向点 (x'_j,y'_j) 和护盾等级 k_j。方向点只指定方向,并不是目的地:飞船经过该点后仍会沿同一方向继续运动。每种方案都从原点、时刻 0 重新开始,不影响其他方案。

对每种方案求飞船被摧毁的时刻;如果它能永远生存,则报告 -1。

输入格式

第一行一个整数 n。

接下来 n 行,每行两个整数 x_i、y_i,表示一个感染点。

接下来一行一个整数 q。

接下来 q 行,每行三个整数 x'_j、y'_j、k_j,表示一种方案的方向点和护盾等级。

数据范围:1≤n≤100000,1≤q≤100000,|x_i|、|y_i|、|x'_j|、|y'_j|≤100000000,1≤k_j≤5。

原题没有保证感染点互不相同,也没有排除原点;相同坐标的多个感染点仍是多个感染圆盘。护盾等级也可能大于 n。

输出格式

输出 q 行,每行对应一种方案:输出飞船被摧毁的时刻;若它永远不会被摧毁,则输出 -1。数值答案的绝对误差或相对误差不超过 10^(-6) 即可。

原题特别规定:方向点 (0,0) 本应是非法情况,但可能出现在输入中。对于这样的询问,直接输出 -1,即使存在位于原点的感染点也是如此。

样例输入 1

5
5 -3
5 4
-6 2
-5 0
4 1
2
-3 -10 1
6 -9 1

样例输出 1

8.700255424092125
3.2260195622572536

样例输入 2

8
4 -1
4 -8
0 9
4 -7
-5 -2
5 -5
7 5
-9 2
10
4 -8 1
7 -7 5
-10 8 2
-9 9 2
4 -7 5
-1 -10 2
6 -3 2
2 -9 3
-10 -10 1
5 9 1

样例输出 2

3.1677629681247024
26.162950903902267
5.461488320163311
6.363961030678928
-1
5.2894082216425735
3.726779962499649
4.6097722286464435
2.9294423792014115
4.7617289402064875