- Описание
- Отправленные решения
23. Канатная дорога
Одному альпинисту очень нравится посещать вершины Уральских гор. Известно, что Уральский хребет не славится высокими горами, однако, его протяжённость впечатляет. Поэтому посещение всех вершин занимает ужасно много времени. Чтобы ускорить этот процесс, альпинист решил построить канатную дорогу.
В качестве отправной точки альпинист выбрал центр своего города. Затем определил координаты всех вершин, относительно этого центра. Оказалось, что все они лежат на одной прямой. Для начала, альпинист решил последовательно соединить вершины канатной дорогой, начиная от центра города. Однако, некоторые горы на этом маршруте оказались слишком низкими и скучными. Поэтому альпинист также решил соединить каждую вершину со следующей, не меньшей по высоте, если такая существует.
План альпиниста очень понравился мэру города! Чтобы правильно составить смету, он попросил вас вычислить суммарную длину такой канатной дороги. Вы против коррупции, поэтому решили произвести расчеты максимально точно.
Формат ввода
Первая строка входных данных содержит целое число $N$ ($1 \le N \le 2 \cdot 10^5$) — количество горных вершин, через которые пройдет канатная дорога. Каждая из следующих $N$ строк содержит два целых числа $x_i, y_i$ ($1 \le x_i, y_i \le 10^9$) — расстояние и высота каждой вершины относительно центра города. Все вершины имеют различные расстояния от центра города и заданы в порядке их возрастания.
Формат вывода
В единственной строке выведите одно число — суммарную длину канатной дороги.
Ваш ответ будет засчитан, если относительная или абсолютная погрешность не будет превышать $10^{-9}$. Формально если $a$ — ваш ответ, а $b$ — ответ жюри, то он будет засчитан если $\frac{|a - b|}{max(b,1)} \le 10^{-9}$.
Примечание
В первом тесте правильный ответ достигается последовательным соединением центра города и всех горных вершин, а также дополнительным соединением первой вершины с третьей и третьей вершины с пятой.
Ограничения
Ограничение времени
2 с
Ограничение памяти
256 МБ
Пример 1
6
3 2
5 1
7 4
9 3
11 7
12 1
31.710272946225