{"problem":{"name":"[ICPC 2020 Shanghai R] Wowoear","description":{"content":"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) commit","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":7000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9819"},"statements":[{"statement_type":"Markdown","content":"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.\n\nThe 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.\n\nHowever, 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.\n\n## Input\n\nThe first line includes a single integer $n$ indicating the number of points on the running trial ($2\\le n\\le 200$).\n\nThe $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$).\n\nIt 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$.\n\nIt 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)$.\n\nIt 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})$.\n\n## Output\n\nOutput the shortest distance Wowo needs to run. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9819","tags":["计算几何","2020","上海","Special Judge","O2优化","线段相交","ICPC"],"sample_group":[["5\n0 0\n1 10\n2 0\n3 10\n4 0","22.099751242242"]],"created_at":"2026-03-03 11:09:25"}}