На плоскости задан источник света. Размеры источника пренебрежимо малы, поэтому его можно считать точкой. Источник движется из точки \((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)\).
Выходные данные
Выведите \(q\) строк. \(i\)-я строка должна содержать единственное действительное число — суммарное время нахождения в тени \(i\)-й точки, пока источник света движется из \((a, s_y)\) в \((b, s_y)\). Ответ будет считаться корректным, если его абсолютная или относительная погрешность не превосходит \(10^{-6}\).
Примечание
- 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)\);
Примеры
| № | Входные данные | Выходные данные |
|
1
|
-3 1 6
2
2 4
6 7
5
3 1
1 3
6 1
6 4
7 6
|
5.000000000000000
3.000000000000000
0.000000000000000
1.500000000000000
2.000000000000000
|