305371: CF1016E. Rest In The Shades
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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. 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