{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e沃沃是一个独自冒险家,在森林、沙漠甚至冰川上完成了许多危险的旅程。上海ICPC(可编程作弊上海邀请赛)委员会邀请沃沃作为他们新的跑步试验的测试者。\u003c/p\u003e\u003cp\u003e这个试验可以描述为一个2D简单的折线$$$(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}$$$相交外,不会互相交叉。任意两个连续的线段有不同的方向。委员会希望沃沃按顺序沿着线段$$$(p_1,p_2),\\ldots, (p_{n-1}, p_n)$$$从$$$p_1$$$跑到$$$p_n$$$。\u003c/p\u003e\u003cp\u003e然而,沃沃有一个可以在一段时间内黑入委员会系统的智能设备。沃沃可以选择$$$2$$$个点$$$a, b$$$在试验中,并直接从$$$a$$$到$$$b$$$沿着线段$$$(a, b)$$$跑。这些$$$a$$$和$$$b$$$可以是一些$$$p_i$$$($$$1\\le i\\le n$$$)也可以是一些线段$$$(p_i, p_{i+1})$$$上的点($$$1\\le i\u0026lt;n$$$)。在到达$$$a$$$之前和之后,沃沃必须沿着原始试验跑。沃沃不想被抓到作弊,所以他决定线段$$$(a, b)$$$不应该在除$$$a$$$和$$$b$$$以外的任何点与试验的任何线段相交或接触。帮助沃沃明智地选择$$$a$$$和$$$b$$$,输出沃沃使用他的智能作弊设备从$$$p_1$$$到$$$p_n$$$需要跑的最短距离。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数$$$n$$$,表示跑步试验上的点数($$$2\\le n\\le 200$$$)。\u003c/p\u003e\u003cp\u003e第$$$i+1$$$行($$$1\\le i\\le n$$$)包含两个整数,用一个空格分隔,表示$$$p_i$$$的坐标($$$-1000\\le x, y\\le 1000$$$)。\u003c/p\u003e\u003cp\u003e保证线段不会互相交叉,除了两个连续的线段$$$(p_i, p_{i+1})$$$和$$$(p_{i+1}, p_{i+2})$$$在点$$$p_{i+1}$$$相交。换句话说,对于任意满足$$$1\\le i\u0026lt; j\u0026lt;n$$$的整数$$$i, j$$$,$$$(p_i, p_{i+1})\\cap (p_{j}, p_{j+1})\u003d\\left\\{\\begin{array}{cc}\\emptyset \u0026amp; i\\neq j-1\\\\ \\{p_{j}\\} \u0026amp; i \u003d j-1\\end{array}\\right.$$$成立。这里$$$(s, t)$$$表示从$$$s$$$到$$$t$$$的线段上的所有点,包括$$$s$$$和$$$t$$$。\u003c/p\u003e\u003cp\u003e保证每个线段的长度不为零。换句话说,对于任何整数$$$i\\in [1, n)$$$,$$$p_i\\neq p_{i+1}$$$。\u003c/p\u003e\u003cp\u003e保证相邻的线段不共线。换句话说,对于任何整数$$$i\\in [1,n-2]$$$和任何实数$$$\\lambda$$$,$$$p_i - p_{i+1}$$$不等于$$$\\lambda(p_{i+1}-p_{i+2})$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出沃沃需要跑的最短距离。如果其绝对或相对误差不超过$$$10^{-6}$$$,则您的答案将被视为正确。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n0 0\n1 10\n2 0\n3 10\n4 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e22.099751242242\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}