Задача №113682. Светофор
Всем известно, что в городах есть большая проблема — пробки. Пробка образуется, когда по дороге пытаются ехать сразу много машин. При этом основная причина образования пробок — перекрестки. Самые большие пробки образуются именно на них.
В одном городе на перекрестке, на котором пересекаются две односторонние дороги, решили установить светофор.
В каждый момент светофор либо горит зеленым для машин на первой дороге, либо горит зеленым для машин на второй дороге, либо переключается между этими режимами. По правилам дорожного движения, в моменты переключения светофора можно ехать по любой дороге.
Светофор устроен следующим образом. В момент времени \(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 \le x \le 10^4
)\), с не более чем тремя знаками
после десятичной точки. Во второй строке задано число
\(n \ (0 \le n \le 100 000)\) — количество машин
на первой дороге. Далее, в \(n\) строках задано описание машин на первой дороге. Описание каждой
машины состоит из двух вещественных чисел \(a_i\) и \(v_i\) — расстояния от машины до перекрестка и
ее скорости, соответственно (\(1 \le a_i
, \ v_i \le 10^4).\) Числа \(a_i\) и \(v_i\) заданы не более, чем с тремя знаками
после десятичной точки.
В следующей строке задано число \(m \ (0 \le m \le 100 000, \ 1 \le n \ + \ m \le 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\), позволяющие добиться искомого. Следует выводить \(g\) и \(r\) не менее чем с 6 знаками после десятичной точки.
Если существует несколько оптимальных решений, выведите любое.
В первом примере все машины подъезжают к перекрестку в момент \(1\). Сделав переключение светофора как раз в этот момент можно обеспечить проезд всех машин без ожидания.
Во втором примере на первой дороге ситуация развивается следующим образом. Сначала через \(1/15\) секунды третья машина догоняет вторую и ей приходится снизить скорость до \(5\) м/с. Затем они вместе догоняют первую машину в момент \(0.5\), им обеим приходится снизить скорость до \(1\) м/с. Так вместе они и подъезжают к перекрестку через \(2\) секунды после начала движения.
На второй дороге машины движутся с равной скоростью и подъезжают к перекрестку через 1, 5 и 7 секунд после начала движения, соответственно. При любом выборе \(g\) и \(r\) хотя бы одной машине придется ждать. Оптимально выбрать любое значение \(g\) от \(2\) до \(3\), включительно. В этом случае ждать будут первая и вторая машины на второй дороге, но одновременно на перекрестке будет находиться не более одной машины. Если выбрать \(g < 2\), то придется ждать трем машинам на первой дороге, а если выбрать \(g > 3\), то вторая и третья машины на второй дороге будут одновременно ждать на перекрестке.
2.0 1 1.0 1.0 2 1.0 1.0 2.0 2.0
0 1.000000000000000 1.000000000000000
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.000000000000000 2.000000000000000