#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