Робот
Робот
Вы участвуете в соревновании по программированию роботов. В следующем соревновании робот должен пройти через n точек на плоскости в определенном порядке. Путь робота должен также удовлетворять следующим условиям:
Каждая часть пути между двумя точками должна быть либо прямой, либо дугой.
Весь путь должен представлять собой гладкую кривую. Это означает, что направления касательных соседних участков пути в общей точке должны совпадать.
Для победы Вам следует найти требуемый путь робота наименьшей длины.
Входные данные
Первая строка содержит количество точек n (2 ≤ n ≤ 1000). Каждая из следующих n строк содержит два целых числа x[i]
и y[i]
, не превосходящих по модулю 10^6
: координаты i-ой точки. Робот должен пройти точки в таком же порядке, в каком они поступают на вход. Каждые две соседние точки различны. Однако не гарантируется, что все входные точки будут различными.
Выходные данные
Вывести одно действительное число: длину кратчайшего пути. Относительная или абсолютная ошибка не должна превосходить 10^(-6)
.
Пример
2 0 0 3 4
5.0000000000
5 1 0 0 1 -1 0 0 -1 1 0
6.2831853072