Задача №1813. Звёздные войны
Игровое поле новой компьютерной игры «Звёздные войны» представляет собой прямоугольник размера \(N*M\). В определённые моменты времени через левую границу игрового поля залетают астероиды, движущиеся с постоянной скоростью \(U\) в горизонтальном направлении. Считается, что все астероиды движутся с одинаковой скоростью. Игрок запускает космические шаттлы из различных точек нижней границы поля. При этом шаттлы движутся в вертикальном направлении с постоянной скоростью \(V\). Известно, что скорость шаттлов больше скорости астероидов.
Безопасность каждого запуска оценивается определённым количеством очков, которое вычисляется следующим образом. Безопасность запуска относительно одного астероида оценивается как минимальное расстояние между шаттлом и астероидом за то время, пока оба объекта находились в пределах игрового поля. Итоговая безопасность запуска оценивается величиной, равной минимальной безопасности запуска относительно каждого из астероидов, побывавших в пределах игрового поля одновременно с шаттлом. Считается, что если объект находится на одной из границ игрового поля \(x\)=0, \(x\)=\(M\), \(y\)=0 или \(y\)=N, то он находится на игровом поле. Под расстоянием между двумя точками \(P_1\)=(\(x_1\), \(y_1\)) и \(P_2\)=(\(x_2\), \(y_2\)) в данной задаче понимается d(\(P_1\), \(P_2\))=|\(x_2\)−\(x_1\)|+|\(y_2\)−\(y_1\)|.
Требуется оценить безопасность каждого из запусков, сделанных игроком. Для простоты астероиды и шаттлы считаются точками. Кроме того, скорость шаттлов \(V\) одинакова для всех запусков.
В первой строке входного файла задаются два целых числа \(N\), \(M\) (1 \(\le\) \(N\), \(M\) \(\le\) \(10^6\)) — размеры игрового поля. Во второй строке заданы два целых числа \(U\) и \(V\) (1 \(\le\) \(U\) < \(V\) \(\le\) 10000) — скорости астероида и шаттлов соответственно.
В третьей строке задано целое число \(K\) (1 \(\le\) \(K\) \(\le\) \(10^5\)) — количество астероидов, побывавших на игровом поле за время игры. В последующих \(K\) строках идёт описание астероидов, каждый из которых задаётся парой целых чисел \(y_i\), \(t_i\) (0 \(\le\) \(y_i\) \(\le\) \(N\), 0 \(\le\) \(t_i\) \(\le\) \(10^6\)) — начальной координатой и моментом появления соответственно. Считается, что астероид появляется в точке с координатами (0, \(y_i\)).
В следующей строке задаётся целое число \(S\) (1 \(\le\) \(S\) \(\le\) \(10^5\)) — количество запусков шаттлов. В последующих \(S\) строках идёт описание запусков, каждый из которых задаётся парой целых чисел \(x_j\), \(t_j\) (0 \(\le\) \(x_j\) \(\le\) \(M\), 0 \(\le\) \(t_j\) \(\le\) \(10^6\)) — координатой и моментом запуска. Запуск производится из точки с координатами (\(x_j\), 0).
Для каждой операции запуска шаттла выведите одно число — оценку безопасности запуска с точностью до \(10^{−3}\). В случае, если одновременно с шаттлом на игровом поле не побывало ни одного астероида, выведите для соответствующего запуска −1. Выводить оценки надо в том же порядке, в котором запуски заданы во входных данных.
5 8 1 2 4 3 0 1 1 2 2 3 3 4 6 5 2 0 1 9 4 100
0.50000 0.50000 6.50000 -1