Rest In The Shades
题意翻译
在第四象限有一个从 $A$ 沿线段 $AB$ 运动到 $B$ 的光源,速度为 $1$ 个单位/秒,在 $x$ 轴正半轴上有 $n$ 条互不重叠的线段,这些线段会遮挡住光线,在动点的运动过程中如图所示产生阴影,给你 $q$ 个第一象限内的点,询问每个点在阴影内的时间为多少秒。
### 输入格式
第$1$行三个整数,$s_y$,$a$,$b$,代表$A$点坐标为$(a,s_y)$,$B$点坐标为$(b,s_y)$
第 $2$ 行一个整数 $n$,代表线段的条数
后 $n$ 行每行 $2$ 个正整数 $l_i,r_i$ 代表一条线段的左端点和右端点
再下一行一个正整数 $q$ 代表询问的点的个数
后 $q$ 行每行两个正整数 $x_i,y_i$ 代表一个询问的点
### 输出格式
$q$ 行每行一个实数代表一次询问的结果,与答案绝对/相对误差在 $10^{-6}$ 内算对
数据范围见英文题面
题目描述
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.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1016E/fd4974e9d648709ca073b5e00e397a0a67168944.png)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) $ .
输入输出格式
输入格式
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.
输出格式
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} $ .
输入输出样例
输入样例 #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
说明
- 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) $ ;