问题描述
平面上有 $n$ 个点,第 $i$ 个点的坐标是 $(x_i , y_i)$。在时刻 $t$,每个点会扩散成一个大小为 $t$ 的,以该点为圆心的圆。注意所有的时间都是均匀连续的。 有一动点 A 初始位于原点,运动速率为 $1$。给定 $q$ 次询问,第 $i$ 次询问给定一个向量 $v = (x'_i, y'_i)$ 和一个数 $k_i$,查询当动点沿向量 $v$ 的方向运动时,第一次被至少 $k_i$ 个圆覆盖时的运动距离。注意 A 越过 $(x'_i, y'_i)$ 后会继续运动。
输入格式
第一行输入一个整数 $n$,接下来 $n$ 行,每行两个整数 $x_i, y_i$。
接下来一行输入一个整数 $q$,接下来 $q$ 行,每行输入三个整数 $x'_i, y'_i, k_i$。
输出格式
对于第 $i$ 次询问,输出一行一个实数,代表第 $i$ 次询问的结果。若可以无限运动下去,输出 $−1$。
绝对或相对误差在 $10^{−6}$ 内算作正确答案。
样例 1 输入
5
5 -3
5 4
-6 2
-5 0
4 1
2
-3 -10 1
6 -9 1
样例 1 输出
8.7002554241
3.2260195623
数据规模与约定
对于所有数据,保证 $1 ≤ n, q ≤ 10^5,|x_i|, |y_i|, |x'_i|, |y'_i| ≤ 10^8,1 ≤ k_i ≤ 5,(x'_i, y'_i)\not= (0, 0)$。
Subtask1(20pts): $n,q\le1000$
Subtask2(25pts): $k_i=1$
Subtask3(20pts): $k_i\le2$
Subtask4(35pts): 无