0326. Рекламное объявление

Ивану с детства нравились газеты. У него даже была мечта стать главным редактором газеты. Однажды ему представился шанс осуществить свою мечту. Чтобы устроиться на работу в издательство, ему необходимо выполнить тестовое задание – сверстать рекламное объявление.

Задано поле шириной W и высотой H. Объявление должно состоять из одной или нескольких строк, в которых необходимо разместить в заданном порядке N слов. Про i-е слово известно, что при печати в стандартном масштабе оно занимает прямоугольник шириной a_i и высотой b_i.

Чтобы объявление выглядело красиво, все слова в нем должны быть напечатаны в одном масштабе. При печати в масштабе k размеры всех слов умножаются на k. Если исходно слово занимало прямоугольник a_i *b_i, то при печати в масштабе k оно занимает прямоугольник размером (k ⋅a_i)*(k ⋅b_i). Кроме того, если в строке более одного слова, то все слова в ней должны иметь одинаковую высоту. Разумеется, ни одно слово не должно выходить за границы поля.

На рисунке приведен пример красивого объявления с тремя словами.

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

Формат входного файла

В первой строке входного файла дано три числа: N, W и H (1 ≤ N ≤ 100,000, 1 ≤ W, H ≤ 10⁹) – число слов в объявлении, длина и высота объявления. В следующих N строках дано по два целых числа, в i-й из них заданы a_i и b_i (1 ≤ a_i, b_i ≤ 10⁹) – ширина и высота i-го слова.

Формат выходного файла

Выведите одно вещественное число k – максимальный масштаб. Ответ требуется вывести с абсолютной или относительной погрешностью не более 10^-9. Это значит, что если правильный ответ a, а вы вывели p, то ваш ответ будет засчитан как правильный, если \frac{|a-p|}{\max(|a|, 1)} ≤ 10^-6.

Пример:

Источник: Командный чемпионат школьников Карелии по программированию, 4 ноября 2012

Обсудить       Отправить решение



Версия для печати