Shortcuts

AtCoder

IDabc315_f

Time2000ms

Memory256MB

Difficulty—

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 other than checkpoints $1$ and $N$ can be skipped. However, let $C$ be the number of checkpoints skipped, and the following penalty will be imposed: * $\displaystyle 2^{C−1}$ if $C>0$, and * $0$ if $C=0$. Let $s$ be the total distance traveled (Euclidean distance) from checkpoint $1$ to checkpoint $N$ plus the penalty. Find the minimum achievable value as $s$. ## Constraints * All input values are integers. * $2 \le N \le 10^4$ * $0 \le X_i,Y_i \le 10^4$ * $(X_i,Y_i) \neq (X_j,Y_j)$ if $i \neq j$. ## Input The input is given from Standard Input in the following format: $N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$ [samples]

Samples

Input #1

Output #1

5.82842712474619009753

Consider passing through checkpoints $1,2,5,6$ and skip checkpoints $3,4$.

*   Move from checkpoint $1$ to $2$. The distance between them is $\sqrt{2}$.
*   Move from checkpoint $2$ to $5$. The distance between them is $1$.
*   Move from checkpoint $5$ to $6$. The distance between them is $\sqrt{2}$.
*   Two checkpoints are skipped, so the penalty of $2$ is imposed.

In this way, you can achieve $s = 3 + 2\sqrt{2} \approx 5.828427$.  
You cannot make $s$ smaller than this value.

Input #2

Output #2

24.63441361516795872523

Input #3

Output #3

110.61238353245736230207

API Response (JSON)

{
  "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 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments