CF1016E.Rest In The Shades

There is a light source on the plane. This source is so small that it can be represented as point. The light source is moving from point $(a, s_y)$ to the $(b, s_y)$ $(s_y \lt 0)$ with speed equal to $1$ unit per second. The trajectory of this light source is a straight segment connecting these two points.

There is also a fence on $OX$ axis represented as $n$ segments $(l_i, r_i)$ (so the actual coordinates of endpoints of each segment are $(l_i, 0)$ and $(r_i, 0)$). The point $(x, y)$ is in the shade if segment connecting $(x,y)$ and the current position of the light source intersects or touches with any segment of the fence.

You are given $q$ points. For each point calculate total time of this point being in the shade, while the light source is moving from $(a, s_y)$ to the $(b, s_y)$.

平面上有一个光源。该光源非常小，可视为一个点。光源从点 $(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)$ 的整个过程中，该点处于阴影中的总时间。

First line contains three space separated integers $s_y$, $a$ and $b$ ($-10^9 \le s_y \lt 0$, $1 \le a \lt b \le 10^9$) — corresponding coordinates of the light source.

Second line contains single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — number of segments in the fence.

Next $n$ lines contain two integers per line: $l_i$ and $r_i$ ($1 \le l_i \lt r_i \le 10^9$, $r_{i - 1} \lt l_i$) — segments in the fence in increasing order. Segments don't intersect or touch each other.

Next line contains single integer $q$ ($1 \le q \le 2 \cdot 10^5$) — number of points to check.

Next $q$ lines contain two integers per line: $x_i$ and $y_i$ ($1 \le x_i, y_i \le 10^9$) — points to process.

第一行包含三个以空格分隔的整数 $s_y$、$a$ 和 $b$（$-10^9 \le s_y \lt 0$，$1 \le a \lt b \le 10^9$）—— 分别表示光源的坐标。

第二行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 围栏中线段的数量。

接下来 $n$ 行，每行包含两个整数：$l_i$ 和 $r_i$（$1 \le l_i \lt r_i \le 10^9$，且 $r_{i - 1} \lt 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$）—— 待处理的点。

Print $q$ lines. The $i$-th line should contain one real number — total time of the $i$-th point being in the shade, while the light source is moving from $(a, s_y)$ to the $(b, s_y)$. The answer is considered as correct if its absolute of relative error doesn't exceed $10^{-6}$.

输出 $q$ 行。第 $i$ 行应包含一个实数——当光源从 $(a, s_y)$ 移动到 $(b, s_y)$ 时，第 $i$ 个点处于阴影中的总时间。若答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

• The 1-st point is always in the shade;

• the 2-nd point is in the shade while light source is moving from $(3, -3)$ to $(6, -3)$;

• the 3-rd point is in the shade while light source is at point $(6, -3)$.

• the 4-th point is in the shade while light source is moving from $(1, -3)$ to $(2.5, -3)$ and at point $(6, -3)$;

• the 5-th point is in the shade while light source is moving from $(1, -3)$ to $(2.5, -3)$ and from $(5.5, -3)$ to $(6, -3)$;

• 第1个点始终处于阴影中；

• 第2个点在光源从 $(3, -3)$ 移动到 $(6, -3)$ 的过程中处于阴影中；

• 第3个点在光源位于点 $(6, -3)$ 时处于阴影中；

• 第4个点在光源从 $(1, -3)$ 移动到 $(2.5, -3)$ 的过程中以及位于点 $(6, -3)$ 时处于阴影中；

• 第5个点在光源从 $(1, -3)$ 移动到 $(2.5, -3)$ 的过程中以及从 $(5.5, -3)$ 移动到 $(6, -3)$ 的过程中处于阴影中。