РОИ: 1 тур

По мотивам фантастической повести

А. и Б. Стругацких «Обитаемый остров»

Правительство страны Неизвестных Отцов планирует построить в гористом районе на границе с Хонтией башню противобаллистической защиты.

Участок горной цепи в этом районе представлен ломаной, состоящей из n звеньев, последовательно соединяющих \(n\) + 1 вершину. Вершины пронумерованы числами от \(0\) до \(n\) в порядке возрастания координаты \(x\). Звенья пронумерованы числами от 1 до \(n\), при этом \(i\)-е звено соединяет вершины с номерами \(i\) − 1 и \(i\).

Вершина с номером 0 находится в точке (0, 0). Звено с номером \(i\) задано двумя числами \(d_i\) — длиной проекции на ось \(x\) и \(k_i\) — угловым коэффициентом. Таким образом, если вершина с номером \(i\) − 1 имеет координаты \((x_{i−1}, y_{i−1})\), то координаты \(i\)-й вершины можно вычислить как \((x_{i − 1} + d_i , y_{i−1} + k_i · d_i)\). Последняя вершина лежит на оси \(x\), то есть \(y_n = 0\).

Башня представлена вертикальным отрезком ненулевой длины, нижняя точка которого расположена на ломаной. Гражданин страны Неизвестных Отцов чувствует себя в безопасности, если верхняя точка башни находится в его прямой видимости.

Пусть верхняя точка башни имеет координаты (\(x, y\)). Два разведчика выбегают из нижней точки башни соответственно на запад (в направлении уменьшения координаты \(x\)) и на восток (в направлении увеличения координаты \(x\)). Каждый разведчик бежит по поверхности горной цепи до тех пор, пока дальнейшее перемещение не выводит верхнюю точку башни из его прямой видимости или до границы горной цепи.

Правительство подготовило \(q\) вариантов расположения башни, каждый из которых характеризуется двумя целыми числами (\(u_j , v_j\)) — координатами верхней точки башни. Требуется написать программу, которая для каждого варианта определяет \(x\)-координаты двух точек, до которых добегут разведчики.