{"raw_statement":[{"iden":"problem statement","content":"There is a race through checkpoints $1,2,\\dots,N$ in this order on a coordinate plane.  \nThe coordinates of checkpoint $i$ are $(X_i,Y_i)$, and all checkpoints have different coordinates.\nCheckpoints other than checkpoints $1$ and $N$ can be skipped.  \nHowever, let $C$ be the number of checkpoints skipped, and the following penalty will be imposed:\n\n*   $\\displaystyle 2^{C−1}$ if $C>0$, and\n*   $0$ if $C=0$.\n\nLet $s$ be the total distance traveled (Euclidean distance) from checkpoint $1$ to checkpoint $N$ plus the penalty.  \nFind the minimum achievable value as $s$."},{"iden":"constraints","content":"*   All input values are integers.\n*   $2 \\le N \\le 10^4$\n*   $0 \\le X_i,Y_i \\le 10^4$\n*   $(X_i,Y_i) \\neq (X_j,Y_j)$ if $i \\neq j$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$X_1$ $Y_1$\n$X_2$ $Y_2$\n$\\vdots$\n$X_N$ $Y_N$"},{"iden":"sample input 1","content":"6\n0 0\n1 1\n2 0\n0 1\n1 0\n2 1"},{"iden":"sample output 1","content":"5.82842712474619009753\n\nConsider passing through checkpoints $1,2,5,6$ and skip checkpoints $3,4$.\n\n*   Move from checkpoint $1$ to $2$. The distance between them is $\\sqrt{2}$.\n*   Move from checkpoint $2$ to $5$. The distance between them is $1$.\n*   Move from checkpoint $5$ to $6$. The distance between them is $\\sqrt{2}$.\n*   Two checkpoints are skipped, so the penalty of $2$ is imposed.\n\nIn this way, you can achieve $s = 3 + 2\\sqrt{2} \\approx 5.828427$.  \nYou cannot make $s$ smaller than this value."},{"iden":"sample input 2","content":"10\n1 8\n3 7\n9 4\n4 9\n6 1\n7 5\n0 0\n1 3\n6 8\n6 4"},{"iden":"sample output 2","content":"24.63441361516795872523"},{"iden":"sample input 3","content":"10\n34 24\n47 60\n30 31\n12 97\n87 93\n64 46\n82 50\n14 7\n17 24\n3 78"},{"iden":"sample output 3","content":"110.61238353245736230207"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}