eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Робот

Робот

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

Вы участвуете в соревновании по программированию роботов. В следующем соревновании робот должен пройти через n точек на плоскости в определенном порядке. Путь робота должен также удовлетворять следующим условиям:

  • Каждая часть пути между двумя точками должна быть либо прямой, либо дугой.

  • Весь путь должен представлять собой гладкую кривую. Это означает, что направления касательных соседних участков пути в общей точке должны совпадать.

Для победы Вам следует найти требуемый путь робота наименьшей длины.

Входные данные

Первая строка содержит количество точек n (2n1000). Каждая из следующих n строк содержит два целых числа x[i] и y[i], не превосходящих по модулю 10^6: координаты i-ой точки. Робот должен пройти точки в таком же порядке, в каком они поступают на вход. Каждые две соседние точки различны. Однако не гарантируется, что все входные точки будут различными.

Выходные данные

Вывести одно действительное число: длину кратчайшего пути. Относительная или абсолютная ошибка не должна превосходить 10^(-6).

Пример

Входные данные #1
2
0 0
3 4
Выходные данные #1
5.0000000000
Входные данные #2
5
1 0
0 1
-1 0
0 -1
1 0
Выходные данные #2
6.2831853072
Источник 2013 Петрозаводск, MIPT contest, Август 25, Задача B