← 返回题目列表

Codeforces · 1016/E

E. 在阴凉处休息

中文机器翻译题面 查看原题

飞机上有光源。该源非常小,可以表示为点。光源从点 $$$(a, s_y)$$$ 移动到 $$$(b, s_y)$$$ $$$(s_y < 0)$$$,速度等于每秒 $$$1$$$ 单位。该光源的轨迹是连接这两点的直线段。

$$$OX$$$ 轴上还有一个栅栏,表示为 $$$n$$$ 段 $$$(l_i, r_i)$$$(因此每个段端点的实际坐标为 $$$(l_i, 0)$$$ 和 $$$(r_i, 0)$$$)。如果连接 $$$(x,y)$$$ 和光源当前位置的线段与围栏的任何线段相交或接触,则点 $$$(x, y)$$$ 位于阴影中。

您将获得 $$$q$$$ 积分。对于每个点,计算该点处于阴影中的总时间,同时光源从 $$$(a, s_y)$$$ 移动到 $$$(b, s_y)$$$。

输入

第一行包含三个空格分隔的整数 $$$s_y$$$、$$$a$$$ 和 $$$b$$$ ($$$-10^9 \le s_y < 0$$$, $$$1 \le a < b \le 10^9$$$) — 对应的光源坐标。

第二行包含单个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 围栏中的段数。

接下来的 $$$n$$$ 行每行包含两个整数:$$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i < r_i \le 10^9$$$, $$$r_{i - 1} < l_i$$$) — 栅栏中的段按升序排列。线段不相交或相互接触。

下一行包含单个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 要检查的点数。

接下来的 $$$q$$$ 行每行包含两个整数:$$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le 10^9$$$) — 指向进程。

输出

打印 $$$q$$$ 行。第 $$$i$$$ 行应包含一个实数 - 当光源从 $$$(a, s_y)$$$ 移动到 $$$(b, s_y)$$$ 时,第 $$$i$$$ 点处于阴影中的总时间。如果相对误差的绝对值不超过 $$$10^{-6}$$$,则答案被认为是正确的。

示例

输入 #1

-3 1 6
2
2 4
6 7
5
3 1
1 3
6 1
6 4
7 6

输出 #1

5.000000000000000
3.000000000000000
0.000000000000000
1.500000000000000
2.000000000000000

注意

- 第一个点始终位于阴影中;
- 当光源从 $$$(3, -3)$$$ 移动到 $$$(6, -3)$$$ 时,第二个点位于阴影中;
- 第三个点位于阴影中,而光源位于点 $$$(6, -3)$$$。
- 当光源从 $$$(1, -3)$$$ 移动到 $$$(2.5, -3)$$$ 并在点 $$$(6, -3)$$$ 时,第 4 个点位于阴影中;
- 当光源从 $$$(1, -3)$$$ 移动到 $$$(2.5, -3)$$$ 以及从 $$$(5.5, -3)$$$ 移动到 $$$(6, -3)$$$ 时,第 5 个点位于阴影中;