{"problem":{"name":"Shortcuts","description":{"content":"There is a race through checkpoints $1,2,\\dots,N$ in this order on a coordinate plane.   The coordinates of checkpoint $i$ are $(X_i,Y_i)$, and all checkpoints have different coordinates. Checkpoints ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc315_f"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   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$.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc315_f","tags":[],"sample_group":[["6\n0 0\n1 1\n2 0\n0 1\n1 0\n2 1","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."],["10\n1 8\n3 7\n9 4\n4 9\n6 1\n7 5\n0 0\n1 3\n6 8\n6 4","24.63441361516795872523"],["10\n34 24\n47 60\n30 31\n12 97\n87 93\n64 46\n82 50\n14 7\n17 24\n3 78","110.61238353245736230207"]],"created_at":"2026-03-03 11:01:14"}}