Задача K. Тянем-потянем
Задачу добавил: alef
Успешно сдано решений: 4
Время на тест 2 с, память 256 Мб
Отдел YYY является одним из потребителей той самой органической пленки, которую выращивает отдел UUU из задачи C. В частности, ленты из такой пленки используются ими в одном очень секретном эксперименте.
Пленка является весьма ценным ресурсом, и ее стараются использовать максимально эффективно. Известно, что лента, изготовленная из пленки, должна иметь толщину не менее d = 1000 — иначе она порвется. Однако на практике получается, что лента на разных участках имеет несколько отличающуюся толщину. Поэтому сотрудники отдела YYY стараются растянуть ее максимально возможным образом.. Структура материала ленты такова, что ее ширина при растяжении не меняется, меняется только толщина.
Когда лента растягивается, она растягивается равномерно, и каждый ее участок испытывает одинаковое относительное удлинение. Понятно, что если в ленте есть участок минимально возможной толщины, то растягивать ее нельзя.
Один из сотрудников отдела предложил использовать специальный фиксатор. Если прижать им ленту в какой-либо точке, то два ее фрагмента можно будет растягивать независимо. Кешу просят написать программу, которая определит, в какой точке поставить фиксатор выгоднее всего.
Формат входного файла input.txt
Первая строка — целое число L (1 ≤ L ≤ 105)— исходная длина ленты.
Вторая строка — целое число N — количество точек на ленте, задающих ее описание
Каждая из следующих N строк содержит пару целых чисел Xj, Dj, где Xj — координата точки на ленте, а Dj (1000 ≤ Dj ≤ 106)— ее толщина в этой точке.
В промежутке между точками Xj и Xj+1 толщина ленты меняется по линейному закону.
Гарантируется, что X0 = 0, XN = L, все координаты расположены в порядке возрастания и попарно различны.
Формат выходного файла output.txt
Первая строка — вещественное число S, длина ленты, которая получится при максимально возможном растяжении с использованием фиксатора. Ответ вывести с точностью не менее 4 знаков после запятой.
Пример входного файла
10
4
0 2000
2 3000
9 10100
10 11000
Пример выходного файла
40.47505030