Wowoear

题号：NC214890
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld

题目描述

Wowo is a solo adventurer who completed many dangerous journeys on his own foot in forests, deserts and even glaciers. The Shanghai ICPC (Shanghai Invitational Contest on Programmable Cheating) committee invited Wowo as a tester of their new running trial.

The trial can be described as a 2D simple polyline $(p_1,\ldots, p_n)$ . In other words, the trial consists of ${n-1}$ line segments $(p_1, p_2),\ldots, (p_{n-1}, p_n)$ . The line segments do not intersect with each other except that two consecutive line segments $(p_i, p_{i+1})$ and $(p_{i+1}, p_{i+2})$ intersect at the point $p_{i+1}$ . Any two consecutive segments have different directions. The committee wants Wowo to run from $p_1$ to $p_n$ along the line segments $(p_1,p_2),\ldots, (p_{n-1}, p_n)$ in order.

However, Wowo has a smart device that can hack the committee's system for an interval of time. Wowo is able to choose 2 points ${a, b}$ on the trial and run directly from ${a}$ to ${b}$ along the line segment ${(a, b)}$ . Each of these ${a}$ and ${b}$ can be some $p_i$ ( $1\le i\le n$ ) and can be some point on some line segment $(p_i, p_{i+1})$ ( $1\le i<n$ ) as well. Before reaching ${a}$ and after reaching ${b}$ , Wowo has to run along the original trial. Wowo does not want to be caught cheating, so he decided that the line segment ${(a, b)}$ should not intersect or touch any line segment of the trial at any point other than ${a}$ and ${b}$ . Help Wowo to choose ${a}$ and ${b}$ wisely and output the shortest distance Wowo need to run from $p_1$ to $p_n$ using his smart cheating device.

输入描述:

The first line includes a single integer  indicating the number of points on the running trial ().

The -th line () contains two integers  and  separated by a single space indicating the coordinates of  ().

It is guaranteed that the line segments do not intersect with each other except that two consecutive line segments  and  intersect at the point . In other words,  holds for any integers  satisfying . Here  represents all points on the line segment from  to  including  and .

It is guaranteed that each line segment has nonzero length. In other words,  for any integer .

It is guaranteed that adjacent line segments are not collinear. In other words, for any integer  and any real number ,  is not equal to .

输出描述:

Output the shortest distance Wowo needs to run. Your answer will be considered correct if its absolute or relative error does not exceed .

示例1

输入

复制

输出

复制

22.099751242242