Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача 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


Задача K

Сдать задачу

Задать вопрос жюри по этой задаче