print2053. Шоссе

printШоссе

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Доктор Реми Хадли, более известная как Тринадцатая, больна хореей Хантингтона. При этой болезни в какой-то момент с человеческим разумом начинают происходить необратимые изменения. В том числе, резко снижаются интеллектуальные способности. Чтобы ни в коем случае не упустить этот момент и вовремя начать агрессивную терапию, Тринадцатая каждую неделю выполняет несложное упражнение, заключающееся в прохождении компьютерной игры.
В игре предлагается перейти шоссе, по которому двигаются автомобили. Шоссе представляет из себя прямоугольник размера `W\ times\ H` метров, а автомобили – прямоугольники меньшего размера, расположенные внутри него. В левом нижнем углу, в точке с координатами (0, 0), расположен человек.
Каждый автомобиль непрерывно двигается по шоссе вправо со скоростью один метр в секунду. При этом, как только автомобиль касается правого края шоссе, он начинает исчезать справа и появляться слева с той же скоростью.
Человеку необходимо перейти шоссе. Как только он решает это сделать, он начинает непрерывно двигаться вертикально вверх со скоростью один метр в секунду. При этом, возможность остановиться у него отсутствует. Если в какой то момент времени он оказывается строго внутри какого-то автомобиля, он умирает. Если же до момента достижения верхней границы шоссе он не касается автомобилей или попадает на их границы, то он успешно переходит шоссе.
Задача доктора Хадли состоит в определении того, может ли человек успешно перейти шоссе. Кроме того, если у него есть эта возможность, необходимо определить количество секунд, через которое он должен начать движение.
В первой строке входного файла заданы два целых числа: `W` и `H` (`4\ ≤\ W,\ H\ ≤\ 10^4`) – длина и ширина шоссе соответственно.
Во второй строке задано целое число `n` (`1\ ≤\ n\ ≤\ 100\ 000`) – количество автомобилей в начальный момент времени.
В следующих `n` строках заданы автомобили, по одному в строке четырьмя целыми числами: `x_1`, `y_1`, `x_2`, `y_2` – координаты противоположных углов соответствующего автомобилю прямоугольника (`0\ ≤\ x_1,\ x_2\ ≤\ W`, `0\ ≤\ y_1,\ y_2\ ≤\ H`, `x_1\ ≠\ x_2`, `y_1\ ≠\ y_2`).
Гарантируется, что прямоугольники, соответствующие автомобилям, не пересекаются и не касаются друг друга.
Если человек может успешно перейти шоссе, в первой строке выходного файла выведите "Yes". Во второй строке выведите одно вещественное число `t` (`0\ ≤\ t\ ≤\ W`) – время в секундах, через которое он может начинать движение. Ответ выводите с максимально возможной точностью.
В противном случае выведите в выходной файл "No".

Пример ввода

8 4
2
0 0 3 2
5 4 7 1

Пример вывода

Yes
3.0
Источник: neerc.ifmo.ru/school
loading