12. Ремонт дороги на Пирогова
До недавнего времени улица Пирогова была почти непроходима для транспорта. Водители легковых автомобилей старались объезжать ее стороной. Наконец, администрация решила сделать на дороге косметический ремонт – заделать все выбоины, причем, в кратчайшие сроки.
Составили план дороги. На плане дорога — прямоугольник, левая сторона которого совпадает с началом координат по оси OX. Отметили на плане все выбоины. Оказалось, что они имеют форму прямоугольников со сторонами, параллельными осям координат, при этом отрезки-проекции выбоин на ось OX не пересекаются.
Время T, которое уходит на заливку одного прямоугольника площадью S вычисляется по формуле: T = t0 + S / v. Ремонтники умеют класть асфальт только прямоугольниками со сторонами, параллельными осям координат, и могут заливать не только одну выбоину отдельно, но и группами, за счет чего может сократиться время работы.
При этом, если большим прямоугольным куском асфальта заливаются с i-ой по j-ю выбоины, по порядку их следования вдоль оси OX, то должны полностью покрыться и все те, что между ними.
Нужно так сгруппировать выбоины, чтобы минимизировать время работы.
Входные данные
В первой строке входного файла записано через пробел три числа n, t0 и v, где n – целое число, количество выбоин на дороге, t0 и v — вещественные числа (1 <= n <= 3000, 0 <= t0 <= 7000 , 0 < v <= 1000) .
В следующих n строках даны координаты выбоин в порядке их встречаемости на плане вдоль оси ОX. Каждая выбоина задается четырьмя вещественными числами — координатами левого нижнего и правого верхнего своих углов. Известно, что ширина дороги не превышает 2000, а длина не больше 3,5*10^6.
Гарантируется, что входные данные таковы, что ответ не превышает 10^8.
Выходные данные
В выходной файл необходимо вывести одно вещественное число с точностью до 10-3 — минимальное время, требуемое для ремонта дороги.
Пример
input.txt
3 7.2 1
1 1 2 3
3 3 4 5
5 2 6 3
output.txt
25.4
Соревнование: XI Открытая Всесибирская олимпиада по программированию имени И.В. Поттосина 2010
Источник: http://olimpic.nsu.ru
| 