Mausoleum

문제

The Mausoleum of King Geo III is a huge stone structure in the shape of a histogram. A histogram is a simple rectilinear polygon whose boundary consists of two chains: an upper chain that is monotone with respect to the horizontal axis, and a lower chain that is a horizontal line segment, called the base segment (see Figure E.1).

Figure E.1. A mausoleum and some paths between $SS$ and $TT$

It is rumored that a hidden treasure lies somewhere within this mausoleum. Metry, a renowned treasure hunter, has uncovered the treasure's location at point $TT$. Metry's plan is to break through the mausoleum's walls, enter, and retrieve the treasure. She will start at a specific location $SS$ outside the mausoleum. Using her equipment, Metry can drill through only one point, which corresponds to a vertex on the boundary of the mausoleum. Since the time required to drill through the walls is the same at all vertices, the key to minimizing the time spent is to find the shortest path from $SS$ to $TT$.

Figure E.1 illustrates a mausoleum along with several possible paths from $SS$ to $TT$, where the vertices are pierced only once. The path through vertex $aa$ has a total length of $11.385165=6+\sqrt{29}11.385165\; =\; 6\; +\; \backslash sqrt\{29\}$, the path through vertex $bb$ has a length of $10.077687=\sqrt{20}+\sqrt{13}+210.077687\; =\; \backslash sqrt\{20\}\; +\; \backslash sqrt\{13\}\; +\; 2$, and the path through vertex $cc$ has a length of $11.0=2+\sqrt{25}+411.0\; =2\; +\; \backslash sqrt\{25\}\; +\; 4$. Among these, the shortest path is through vertex $bb$.

Given the boundary of the mausoleum and the positions of $SS$ and $TT$, write a program to find the length of the shortest path from $SS$ to $TT$ with a single vertex piercing.

입력

Your program is to read from standard input. The input starts with a line containing an integer, $nn$ (4 ≤ n ≤100\,000), where $nn$ is even and is the number of vertices of a histogram representing the mausoleum. In the second line, $nn$ integers $v_1,v_2,\dots ,v_{n}v\_1\; ,\; v\_2\; ,\; \backslash dots\; ,\; v\_n$ ($v_1=v_n=0v\_1\; =\; v\_n\; =\; 0$, 0 ≤ v_i ≤ 10^6) are given, which represent the $xx$-coordinates of the vertical edges and the $yy$-coordinates of the horizontal edges. The vertical and horizontal edges alternate as you traverse the upper chain of the histogram, from the left end to the right end of the base segment. The length of each edge is at least $11$, and the $xx$-coordinates are given in strictly increasing order. The last line contains four integers $s_{x}s\_x$, $s_{y}s\_y$, $t_{x}t\_x$, and $t_{y}t\_y$ (-10^6 ≤ s_x, s_y ≤ 2 \times 10^6, ), where $(s_x,s_y)(s\_x,\; s\_y)$ and $(t_x,t_y)(t\_x,\; t\_y)$ correspond to the points $SS$ and $TT$, respectively. Notice that $SS$ is a point outside the histogram and $TT$ is a point inside the histogram, neither of which lies on the boundary.

출력

Your program is to write to standard output. Print exactly one line. The line should contain exactly one real value which is the length of the shortest path between $SS$ and $TT$. Your output $zz$ should be in the format that consists of its integer part, a decimal point, and its fractional part, and will be decided to be “correct” if it holds that , where $aa$ denotes the jury’s answer. The Euclidean distance between two points $p=(x_1,y_1)p\; =\; (x\_1,\; y\_1)$ and $q=(x_2,y_2)q\; =\; (x\_2,\; y\_2)$ is $\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}\backslash sqrt\{(x\_1\; -\; x\_2)^2\; +\; (y\_1\; -\; y\_2)^2\}$.

12
0 5 2 8 5 3 7 6 11 4 13 0
11 8 3 3

10.077687

8
0 7 2 2 5 7 7 0
-2 4 6 4

11.767829

4
0 5 8 0
8 6 4 2

6.0