19885번 - Светофор 스페셜 저지다국어

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

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

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

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

Таким образом, светофор горит зеленым для первой дороги в моменты времени $\left( k(r + g), k(r + g) + g\right)$ для целых $k$ и зеленым для второй дороги --- в $\left( k(r + g) + g, (k + 1)(r + g) \right)$. Переключения же происходят в моменты $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 \le x \le 10^4$), с не более чем тремя знаками после десятичной точки. Во второй строке задано число $n$ ($0 \le n \leq 100\,000$) --- количество машин на первой дороге. Далее, в $n$ строках задано описание машин на первой дороге. Описание каждой машины состоит из двух вещественных чисел $a_i$ и $v_i$ --- расстояния от машины до перекрестка и ее скорости, соответственно ($1 \le a_i, v_i \leq 10^4$). Числа $a_i$ и $v_i$ заданы не более, чем с тремя цифрами после десятичной точки.

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

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

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

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

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

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

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