Вы можете зарегистрироваться и решать эту задачу здесь.
| Ограничение времени: | 3 с |
| Ограничение реального времени: | 6 с |
| Ограничение памяти: | 256M |
Театр теней
Тиктокеры Стас и Ян, постояльцы палаты номер 66 заведения «Покосившийся Скворечник», решили устроить перфоманс в прямом эфире. Они разместили на прямоугольном полу своей палаты n свечей в разных точках и готовятся провести представление, состоящее из m актов. В каждом акте должен гореть только определённый набор свечей, который будет таким образом создавать новую картину из теней на стене палаты, остальные свечи должны быть потушены. Область, попадающая в кадр, имеет ширину w, длину l, по ширине перекрывает палату целиком, а по длине оставляет небольшое пространство слева и справа, как показано на рисунке.
Сами тиктокеры в кадре появляться не должны, с этой целью они могут находиться либо у левой, либо у правой стенки палаты за кадром. Чтобы тушить и зажигать свечи, Стас и Ян могут делать перерывы между актами перфоманса, во время которых стрим отключается, и они будут выбегать в кадр: Стас будет только зажигать свечи, а Ян – только гасить, после чего они должны успеть скрыться из кадра до начала нового акта. Перед перфомансом Стас находится за кадром слева, а Ян – за кадром справа. Также изначально зажжены свечи, необходимые для первого акта.
Чтобы подписота не заскучала без зрелища и не разбрелась смотреть рэп-батлы, перерывы между актами должны суммарно занимать как можно меньше времени. Найдите это время и тиктокеры подарят Вам золотую подписку на их канал!
Первая строка ввода содержит пять чисел – w, l, v1, v2 и n (1 ≤ w, l ≤ 50, 1 ≤ v1, v2 ≤ 20, 1 ≤ n ≤ 15) – размеры кадра, скорости Стаса и Яна и количество свечей на полу. Далее идут n строк с координатами свечей xi, yi (0 < xi < l, 0 < yi < w). Следующая строка содержит число m (1 ≤ m ≤ 104) – количество актов перфоманса. Далее идут m строк, каждая из которых начинается с количества свечей, которые должны гореть в очередном акте и продолжается номерами этих свечей.
Единственная строка вывода должна содержать число – минимально возможное суммарное время перерывов между актами перфоманса с точностью до 10-5.
Примеры
| Входные данные | Результат работы |
|
5 6 1 1 3 1 2 3 4 5 3 1 1 3 |
0.000000 |
|
5 6 1 1 3 1 2 3 4 5 3 3 1 3 2 1 2 3 1 2 3 |
8.828427 |
Видеоразбор решения задачи здесь.