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