Рабочее место участника

Всем известно, что в городах есть большая проблема — пробки. Пробка образуется, когда по дороге пытаются ехать сразу много машин. При этом основная причина образования пробок — перекрестки. Самые большие пробки образуются именно на них.

В одном городе на перекрестке, на котором пересекаются две односторонние дороги, решили установить светофор.

В каждый момент светофор либо горит зеленым для машин на первой дороге, либо горит зеленым для машин на второй дороге, либо переключается между этими режимами. По правилам дорожного движения, в моменты переключения светофора можно ехать по любой дороге.

Светофор устроен следующим образом. В момент времени `0` он загорается зеленым для машин на первой дороге и красным для машин на второй дороге. Далее, через `g` секунд он переключается на красный для машин на первой дороге и зеленый для машин на второй дороге, после чего через `r` секунд переключается обратно на зеленый для первой дороги, и т. д.

Таким образом, светофор горит зеленым для первой дороги в моменты времени `(\ k(r\ +\ g),\ k(r\ +\ g)\ +\ g)` для целых `k` и зеленым для второй дороги — в `(\ k(r\ +\ g)\ +\ g,\ (k\ +\ 1)(r\ +\ g)\ )`. Переключения же происходят в моменты `k(r\ +\ g)` и `k(r\ +\ g)\ +\ g`. Когда светофор горит зеленым для первой дороги, по ней могут ехать машины, а по второй — нет, и наоборот. Будем считать что в момент переключения, могут проезжать машины с обеих дорог. Считается что машина проехала в момент переключения, если момент, когда она проехала, и момент переключения отличаются не более чем на `10^{-5}`.

В соответствии с технической документацией период работы светофора зафиксирован и должен быть равен `x`, иначе говоря, должно выполняться равенство `r\ +\ g\ =\ x`. С соблюдением этого условия значения `r` и `g` можно выбрать любыми неотрицательными вещественными числами.

Для выбора оптимальных значений `r` и `g` было проведено исследование трафика на дорогах и получены следующие данные.

На каждой из дорог находится несколько машин, которые едут в сторону перекрестка. Машины не обгоняют друг друга. Каждый раз, когда машина догоняет более медленную, она снижает скорость и следует непосредственно за ней с соответствующей скоростью. Размерами машин и временем на изменение скорости можно пренебречь. Когда машина подъезжает к перекрестку, если горит зеленый свет или происходит переключение, то она немедленно проезжает перекресток. В противном случае машина останавливается и ждет включения зеленого света.

В момент 0 на первой дороге расположены `n` машин, `i`-я из них находится на расстоянии `a_i` метров от перекрестка и движется в его сторону со скоростью `v_i` м/с.

Аналогично, на второй дороге расположены `m` машин, `i`-я из них находится на расстоянии `b_i` метров от перекрестка и движется в его сторону со скоростью `w_i` м/с.

Чтобы пробок в городе было меньше, необходимо выбрать такие `g` и `r`, чтобы максимальное число машин, которые одновременно стоят на перекрестке, было как можно меньше.

Помогите управлению дорожного движения выбрать оптимальные `g` и `r`.

В первой строке задано вещественное число `x` (`1\ ≤\ x\ ≤\ 10^4`), с не более чем тремя знаками после десятичной точки. Во второй строке задано число `n` (`0\ ≤\ n\ ≤\ 100\ 000`) — количество машин на первой дороге. Далее, в `n` строках задано описание машин на первой дороге. Описание каждой машины состоит из двух вещественных чисел `a_i` и `v_i` — расстояния от машины до перекрестка и ее скорости, соответственно (`1\ ≤\ a_i,\ v_i\ ≤\ 10^4`). Числа `a_i` и `v_i` заданы не более, чем с тремя знаками после десятичной точки.

В следующей строке задано число `m` (`0\ ≤\ m\ ≤\ 100\ 000`, `1\ ≤\ n\ +\ m\ ≤\ 100\ 000`) — количество машин на второй дороге. Далее, в `m` строках задано описание машин на второй дороге. Описание каждой машины состоит из двух вещественных чисел `b_i` и `w_i` — расстояния от машины до перекрестка и ее скорости, соответственно (`1\ ≤\ b_i,\ w_i\ ≤\ 10^4`). Числа `b_i` и `w_i` заданы не более, чем с тремя знаками после десятичной точки.

Никакие две машины исходно не находятся в одной точке. Оба списка машин даны в порядке возрастания расстояния до светофора.

На первой строке выходного файла выведите минимальное `k`, такое что выбором `g` и `r` можно добиться, чтобы на перекрестке никогда не стояло одновременно более `k` машин.

На второй строке выведите два вещественных числа `g` и `r`, позволяющие добиться искомого. Следует выводить `g` и `r` не менее чем с 6 знаками после десятичной точки.

Если существует несколько оптимальных решений, выведите любое.

2.0
1 
1.0 1.0
2
1.0 1.0
2.0 2.0

0
1.00000 1.00000

4.0
3 
2.0 1.0
4.0 5.0
5.0 20.0
3
1.0 1.0
5.0 1.0
7.0 1.0

1
2.00000 2.00000

В первом примере все машины подъезжают к перекрестку в момент 1. Сделав переключение светофора как раз в этот момент можно обеспечить проезд всех машин без ожидания.

Во втором примере на первой дороге ситуация развивается следующим образом. Сначала через `1/15` секунды третья машина догоняет вторую и ей приходится снизить скорость до 5 м/с. Затем они вместе догоняют первую машину в момент 0.5, им обеим приходится снизить скорость до 1 м/с. Так вместе они и подъезжают к перекрестку через 2 секунды после начала движения.

На второй дороге машины движутся с равной скоростью и подъезжают к перекрестку через 1, 5 и 7 секунд после начала движения, соответственно. При любом выборе `g` и `r` хотя бы одной машине придется ждать. Оптимально выбрать любое значение `g` от 2 до 3, включительно. В этом случае ждать будут первая и вторая машины на второй дороге, но одновременно на перекрестке будет находиться не более одной машины. Если выбрать `g\ <\ 2`, то придется ждать трем машинам на первой дороге, а если выбрать `g\ >\ 3`, то вторая и третья машины на второй дороге будут одновременно ждать на перекрестке.