English · Original
Chinese · Translation
Formal · Original
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 < 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.
<center></center>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)$.
## Input
First line contains three space separated integers $s_y$, $a$ and $b$ ($-10^9 \le s_y < 0$, $1 \le a < 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 < r_i \le 10^9$, $r_{i - 1} < 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.
## Output
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}$.
[samples]
## Note
* 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)$;
在平面上有一个光源。这个光源非常小，可以表示为一个点。光源从点 $(a, s_y)$ 移动到点 $(b, s_y)$（其中 $s_y < 0$），速度为每秒 1 单位。光源的轨迹是连接这两点的直线段。
在 $O X$ 轴上有一个由 $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 \leq s_y < 0$，$1 \leq a < b \leq 10^9$）——光源的对应坐标。
第二行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）——围栏的线段数量。
接下来 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i < r_i \leq 10^9$，$r_{i -1} < l_i$）——按递增顺序排列的围栏线段。这些线段互不相交且不相触。
下一行包含一个整数 $q$（$1 \leq q \leq 2 \cdot 10^5$）——待检查的点的数量。
接下来 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq 10^9$）——待处理的点。
输出 $q$ 行。第 $i$ 行应包含一个实数——第 $i$ 个点在光源从 $(a, s_y)$ 移动到 $(b, s_y)$ 过程中处于阴影中的总时间。若答案的绝对误差或相对误差不超过 $10^{-6}$，则认为正确。
## Input
第一行包含三个用空格分隔的整数 $s_y$、$a$ 和 $b$（$-10^9 \leq s_y < 0$，$1 \leq a < b \leq 10^9$）——光源的对应坐标。第二行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）——围栏的线段数量。接下来 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i < r_i \leq 10^9$，$r_{i -1} < l_i$）——按递增顺序排列的围栏线段。这些线段互不相交且不相触。下一行包含一个整数 $q$（$1 \leq q \leq 2 \cdot 10^5$）——待检查的点的数量。接下来 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq 10^9$）——待处理的点。
## Output
输出 $q$ 行。第 $i$ 行应包含一个实数——第 $i$ 个点在光源从 $(a, s_y)$ 移动到 $(b, s_y)$ 过程中处于阴影中的总时间。若答案的绝对误差或相对误差不超过 $10^{-6}$，则认为正确。
[samples]
## Note
第一个点始终在阴影中；第二个点在光源从 $(3, -3)$ 移动到 $(6, -3)$ 时处于阴影中；第三个点在光源位于点 $(6, -3)$ 时处于阴影中；第四个点在光源从 $(1, -3)$ 移动到 $(2.5, -3)$ 以及位于点 $(6, -3)$ 时处于阴影中；第五个点在光源从 $(1, -3)$ 移动到 $(2.5, -3)$ 以及从 $(5.5, -3)$ 移动到 $(6, -3)$ 时处于阴影中；
**Definitions**
Let $ s_y < 0 $ be the constant $ y $-coordinate of the light source.
Let $ a, b \in \mathbb{R} $ with $ a < b $, such that the light source moves along the line segment from $ (a, s_y) $ to $ (b, s_y) $ at speed 1 unit per second.
Let $ \mathcal{F} = \{ (l_i, r_i) \}_{i=1}^n $ be a set of $ n $ disjoint closed intervals on the $ x $-axis, representing the fence segments, with $ l_i < r_i $ and $ r_{i-1} < l_i $ for all $ i \geq 2 $.
Let $ P = \{ (x_j, y_j) \}_{j=1}^q $ be a set of $ q $ query points in the plane, with $ y_j > 0 $.
Let $ L(t) = (x(t), s_y) $ denote the position of the light source at time $ t \in [0, T] $, where $ T = b - a $, and $ x(t) = a + t $.
A point $ p = (x_j, y_j) $ is **in the shade** at time $ t $ if the line segment from $ L(t) $ to $ p $ intersects or touches at least one fence segment $ (l_i, r_i) \times \{0\} $.
**Constraints**
1. $ -10^9 \leq s_y < 0 $
2. $ 1 \leq a < b \leq 10^9 $
3. $ 1 \leq n \leq 2 \cdot 10^5 $, $ 1 \leq l_i < r_i \leq 10^9 $, $ r_{i-1} < l_i $
4. $ 1 \leq q \leq 2 \cdot 10^5 $, $ 1 \leq x_j, y_j \leq 10^9 $
**Objective**
For each query point $ p_j = (x_j, y_j) $, compute the total measure of time $ t \in [0, b - a] $ during which the segment $ \overline{L(t) p_j} $ intersects or touches at least one fence segment $ [l_i, r_i] \times \{0\} $.
That is, compute:
$$
T_j = \mu\left( \left\{ t \in [0, b - a] \ \middle|\ \exists i \in \{1, \dots, n\} \text{ s.t. } \overline{L(t) p_j} \cap \left( [l_i, r_i] \times \{0\} \right) \neq \emptyset \right\} \right)
$$
where $ \mu $ denotes Lebesgue measure on $ \mathbb{R} $.
API Response (JSON)
{
"problem": {
"name": "E. Rest In The Shades",
"description": {
"content": "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 < 0)$ with speed equal to",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1016E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 < 0)$ with speed equal to...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在平面上有一个光源。这个光源非常小，可以表示为一个点。光源从点 $(a, s_y)$ 移动到点 $(b, s_y)$（其中 $s_y < 0$），速度为每秒 1 单位。光源的轨迹是连接这两点的直线段。\n\n在 $O X$ 轴上有一个由 $n$ 个线段 $(l_i, r_i)$ 表示的围栏（因此每个线段的实际端点坐标为 $(l_i, 0)$ 和 $(r_i, 0)$）。点 $(x, y)$ 被称为 _...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ s_y < 0 $ be the constant $ y $-coordinate of the light source. \nLet $ a, b \\in \\mathbb{R} $ with $ a < b $, such that the light source moves along the line segment from $ (a,...",
"is_translate": false,
"language": "Formal"
}
]
}