Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:1024 MB
统计

问题描述

平面上有 $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): 无

大样例