Задача №113665. Рекламное объявление
Ивану с детства нравились газеты. У него даже была мечта стать главным редактором газеты. Однажды ему представился шанс осуществить свою мечту. Чтобы устроиться на работу в издательство, ему необходимо выполнить тестовое задание — сверстать рекламное объявление.
Задано поле шириной \(W\) и высотой \(H\). Объявление должно состоять из одной или нескольких строк, в которых необходимо разместить в заданном порядке \(N\) слов. Про \(i\)-е слово известно, что при печати в стандартном масштабе оно занимает прямоугольник шириной \(a_i\) и высотой \(b_i.\)
Чтобы объявление выглядело красиво, все слова в нем должны быть напечатаны в одном масштабе. При печати в масштабе \(k\) размеры всех слов умножаются на \(k\). Если исходно слово занимало прямоугольник \(a_i \times b_i\) , то при печати в масштабе \(k\) оно занимает прямоугольник размером \((k \cdot a_i) \times (k \cdot b_i)\). Кроме того, если в строке более одного слова, то все слова в ней должны иметь одинаковую высоту. Разумеется, ни одно слово не должно выходить за границы поля.
На рисунке приведен пример красивого объявления с тремя словами.
В первой строке входного файла дано три числа: \(N, \ W \ и \ H \ (1 \le N \le 100 000, 1 \le W, \ H \le 10^9 )\) — число слов в объявлении, длина и высота объявления. В следующих \(N\) строках дано по два целых числа, в \(i\)-й из них заданы \(a_i\) и \(b_i\) (\(1 \le a_i \ , b_i \le 10^9\) ) — ширина и высота \(i\)-го слова.
Выведите одно вещественное число \(k\) — максимальный масштаб. Ответ требуется вывести с
абсолютной или относительной погрешностью не более \(10^{−9}.\)
Это значит, что если правильный ответ
\(a\), а вы вывели \(p\), то ваш ответ будет засчитан как правильный, если \(\frac{|a \ - \ p|}{
max(|a|, \ 1)} \le 10^{−6}.\)
3 10 7 4 3 3 2 4 2
1.400000000000000
2 10 1 2 1 3 2
0.333333333333333