s111. C. Bitonic Path - 高中生程式解題系統

內容

在平面上有 $n$ 個點，編號 $1$ 到 $n$，它們的 $x$ 座標嚴格遞增（即 $x_1<x_2<⋯<x_n$）。我們想要找一條從點 $1$ 出發，到達點 $n$，然後再返回點 $1$ 的路徑，滿足：

每個點恰好經過一次。
路徑在去程和回程中都是單調的：去程時 $x$ 座標嚴格遞增，回程時 $x$ 座標嚴格遞減。

換句話說，整條路徑形成一個「雙調」環路，即從點 $1$ 開始，先經過一些點（依 $x$ 遞增方向）到達點 $n$，然後再經過剩餘的點（依 $x$ 遞減方向）回到點 $1$，並且每個點恰好出現一次。

請計算這樣的最短路徑長度（歐幾里得距離）。輸出四捨五入到小數點後兩位。

輸入說明

第一行包含一個整數 $n$，表示點的數量。
接下來 $n$ 行，每行兩個整數 $x_i,y_i$，表示第 $i$ 個點的座標。輸入保證 $x_i$ 嚴格遞增。

$2≤n≤2000$
$−10^4≤x_i,y_i≤10^4$
$x_i$ 嚴格遞增

輸出說明

輸出一個實數，表示最短路徑長度，四捨五入保留兩位小數。

範例輸入 #1

範例輸出 #1

6.83

測資資訊：

記憶體限制： 256 MB
不公開測資點#0 (5%): 0.1s , <1M
不公開測資點#1 (5%): 0.1s , <1M
不公開測資點#2 (5%): 0.1s , <1M
不公開測資點#3 (5%): 0.1s , <1M
不公開測資點#4 (5%): 0.1s , <1M
不公開測資點#5 (5%): 0.1s , <1M
不公開測資點#6 (5%): 0.1s , <1M
不公開測資點#7 (5%): 0.1s , <1M
不公開測資點#8 (5%): 0.1s , <1M
不公開測資點#9 (5%): 0.1s , <1M
不公開測資點#10 (5%): 0.1s , <1M
不公開測資點#11 (5%): 0.1s , <1M
不公開測資點#12 (5%): 0.1s , <1M
不公開測資點#13 (5%): 0.1s , <1M
不公開測資點#14 (5%): 0.1s , <1M
不公開測資點#15 (5%): 0.1s , <1M
不公開測資點#16 (5%): 0.1s , <1M
不公開測資點#17 (5%): 0.1s , <1M
不公開測資點#18 (5%): 0.1s , <1M
不公開測資點#19 (5%): 0.1s , <1M

提示：

最短路徑為 $1 \to 2 \to 4 \to 3 \to 1$，長度為

\[
\sqrt{(1-0)^2 + (1-0)^2} + \sqrt{(3-1)^2 + (1-1)^2} + \sqrt{(3-2)^2 + (1-0)^2} + \sqrt{(2-0)^2 + (0-0)^2}
\]

\[
\approx 1.414 + 2.0 + 1.414 + 2.0 = 6.828
\]

四捨五入為 $6.83$。

標籤:

練習賽(一) Zaim

出處:

[管理者：

chenwei98050 ... (陳維（Z）) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」