题目描述

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 $n$ indicating the number of points on the running trial ($2\le n\le 200$).

The $i+1$-th line ($1\le i\le n$) contains two integers $x$ and $y$ separated by a single space indicating the coordinates of $p_i$ ($-1000\le x, y\le 1000$).

It is guaranteed that 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}$. In other words, $(p_i, p_{i+1})\cap (p_{j}, p_{j+1})=\left\{\begin{array}{cc}\emptyset & i\neq j-1\\ \{p_{j}\} & i = j-1\end{array}\right.$ holds for any integers $i, j$ satisfying $1\le i< j<n$. Here $(s, t)$ represents all points on the line segment from $s$ to $t$ including $s$ and $t$.

It is guaranteed that each line segment has nonzero length. In other words, $p_i\neq p_{i+1}$ for any integer $i\in [1, n)$.

It is guaranteed that adjacent line segments are not collinear. In other words, for any integer $i\in [1,n-2]$ and any real number $\lambda$, $p_i - p_{i+1}$ is $\textbf{not}$ equal to $\lambda(p_{i+1}-p_{i+2})$.

输出格式

Output the shortest distance Wowo needs to run. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

题目大意

题目描述

Wowo 是一位单人冒险家，他曾独自一人在森林、沙漠甚至冰川中完成过许多危险的旅程。ICPC（上海市可编程作弊邀请赛）组委会邀请 Wowo 作为新的跑步测试员。

该试验可描述为二维简单折线 $(p_1,\ldots, p_n)$。换句话说，试验由 $n-1$ 条线段 $(p_1, p_2),\ldots, (p_{n-1}, p_n)$ 组成。除了两个连续的线段 $(p_i, p_{i+1})$ 和 $(p_{i+1}, p_{i+2})$ 相交于点 $p_{i+1}$ 外，其他线段互不相交。任何两条连续的线段都有不同的方向。委员会希望 Wowo 从 $p_1$ 到 $p_n$ 依次沿着线段 $(p_1,p_2),\ldots, (p_{n-1}, p_n)$ 运行。

然而，Wowo 拥有一个智能设备，可以在一段时间内侵入委员会的系统。Wowo 能够在试验中选择 $2$ 点 $a, b$ ，并沿着线段 $(a, b)$ 直接从 $a$ 跑到 $b$ 。其中每个 $a$ 和 $b$ 都可以是某个 $p_i$ （$1\le i\le n$）。($1\le i\le n$) ，也可以是线段 $(p_i, p_{i+1})$ 上的某一点。($1\le i \le n$)上的某一点。在到达 $a$ 之前和 $b$ 之后，Wowo 必须沿着原来的试验路线运行。沃沃不想被发现作弊，所以他决定线段 $(a, b)$ 不能与试验中的任何线段相交，也不能接触到 $a$ 和 $b$ 以外的任何点。请帮助 Wowo 明智地选择 $a$ 和 $b$ ，并利用他的智能作弊装置输出 Wowo 需要从 $p_1$ 跑到 $p_n$ 的最短距离

输入格式

第一行包含一个整数 $n$ ，表示运行试验中的点数（ $2\le n\le 200$ ）。

第 $i+1$（$1\le i\le n$）行包含两个整数 $x$ 和 $y$，中间用一个空格隔开，表示 $p_i$（$-1000\le x, y\le 1000$）的坐标。

除了两条连续的线段 $(p_i, p_{i+1})$ 和 $(p_{i+1}, p_{i+2})$ 相交于点 $p_{i+1}$ 之外，其他线段保证互不相交。换句话说，对于满足 $1 \le i\lt j \lt n$ 的任何整数 $i, j$，$(p_i, p_{i+1})\cap (p_{j}, p_{j+1})=\left\{\begin{array}{cc}\emptyset & i\neq j-1\\ \{p_{j}\} & i = j-1\end{array}\right.$ 都成立。这里的 $(s, t)$ 代表从 $s$ 到 $t$ 的线段上的所有点，包括 $s$ 和 $t$。 可以保证每条线段的长度都不为零。换句话说，$p_i\neq p_{i+1}$ 满足任意整数 $i\in [1, n)$。

保证相邻线段不相交。换句话说，对于任意整数 $i\in [1,n-2]$ 和任意实数 $\lambda$，$p_i - p_{i+1}$ 不等于$\lambda(p_{i+1}-p_{i+2})$。

输出格式

输出 Wowo 需要运行的最短距离。如果答案的绝对误差或相对误差不超过 $10^{-6}$，则认为答案正确。
Translation by nightwatch_ryan

5
0 0
1 10
2 0
3 10
4 0

22.099751242242