因此,我们感到无聊,并决定自行猜测,如果电影的预算非常低,《盗梦空间》的制作会如何进行。
我们记得的第一个场景是整个城市向自身弯曲的场景:
感觉CGI费用会很高吧?幸运的是,我们想出了一个类似的场景,而且制作成本稍微便宜一些。
首先,忘记 3D,那很难而且昂贵!城市现在用一条数轴表示(当然,无限是为了更容易理解)。
其次,城市不必看起来很自然。线路上有 $$$n$$$ 建筑物。每栋建筑都是一个正方形 $$$1 \times 1$$$。建筑物按照其位置的升序从 $$$1$$$ 到 $$$n$$$ 编号。建筑物 $$$i$$$ 的下角位于数轴的整数点 $$$a_i$$$ 和 $$$a_i + 1$$$ 处。此外,任何两个相邻建筑物 $$$i$$$ 和 $$$i + 1$$$ 之间的距离不超过 $$$d$$$ (实际上,这个条件只是为了让城市看起来不那么稀疏)。一些相邻建筑物 $$$i$$$ 和 $$$i + 1$$$ 之间的距离是从建筑物 $$$i$$$ 的右下角到建筑物 $$$i + 1$$$ 的左下角计算的。
最后,弯曲的曲率也很难模拟!使用以下算法在某个整数坐标 $$$x$$$ 处进行弯曲。将射线从 $$$x$$$ 带到 $$$+\infty$$$ 以及该射线上的所有建筑物,并开始围绕点 $$$x$$$ 逆时针旋转射线和建筑物。在某些角度,某些建筑物会接触到另一建筑物或线路的一部分。你必须停止在那里弯腰(实施建筑物粉碎也不值得花钱)。
我们将最终状态下两条射线之间的角度称为终端角 $$$\alpha_x$$$。
剩下的唯一事情就是决定哪个整数点$$$x$$$最适合开始弯曲。幸运的是,我们已经选择了 $$$m$$$ 候选者来执行弯曲。
那么,您能帮我们计算候选列表中每个弯曲 $$$x$$$ 的终端角度 $$$\alpha_x$$$ 吗?
输入
第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le d \le 7000$$$) — 分别是建筑物的数量和任意一对相邻建筑物之间的最大距离。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$a_1 = 0$$$, $$$0 < a_{i + 1} - a_i \le d + 1$$$) — 相应建筑物左上角的坐标,按升序排列。
第三行包含单个整数 $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — 候选者的数量。
第四行包含 $$$m$$$ 整数 $$$x_1, x_2, \dots, x_m$$$ ($$$0 \le x_i \le a_n + 1$$$, $$$x_i < x_{i + 1}$$$) — 您需要按升序计算终端角度的弯曲坐标。
输出
打印 $$$m$$$ 数字。对于每个弯曲 $$$x_i$$$ 打印终端角度 $$$\alpha_{x_i}$$$ (以弧度为单位)。
如果您的答案的绝对误差不超过 $$$10^{-9}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$|a - b| 时,您的答案才会被接受\le 10^{-9}$$$。
示例
输入 #1
3 5 0 5 7 9 0 1 2 3 4 5 6 7 8
输出 #1
1.570796326794897 1.570796326794897 0.785398163397448 0.927295218001612 0.785398163397448 1.570796326794897 1.570796326794897 1.570796326794897 1.570796326794897
输入 #2
2 7 0 4 3 1 3 4
输出 #2
1.570796326794897 0.927295218001612 1.570796326794897
输入 #3
5 0 0 1 2 3 4 6 0 1 2 3 4 5
输出 #3
1.570796326794897 3.141592653589793 3.141592653589793 3.141592653589793 3.141592653589793 1.570796326794897
注意
在这里您可以看到第一个示例的城市图片以及位置 $$$2$$$ 处的弯道。您需要测量的角度标记为蓝色。您可以看到它等于 $$$\frac \pi 4$$$。
您可以看到,没有一对相邻建筑物之间的距离超过 $$$4$$$。 $$$d = 4$$$ 也足以满足该测试。