還記得小向嗎?對,就是那個天龍國的天才魔法少女。
身為天龍國的天才魔法少女,在時空中穿梭是一定要的,小向常常使用她的神奇魔法到處旅行。
有天,小向突然很想要進行時空穿梭,她決定要從她所在的位置開始她的奇幻旅程。
這時候問題就來了,
我們都知道,時空旅行其實就是一個在時間和空間組成的二維平面座標上面旅行(橫軸是時間,縱軸是空間),小向使用她的魔法算出了她的幾個想要旅行的時空座標,並且將她標示在魔法導航器上,但是這個魔法導航器只能算出兩點間的時空距離,卻不能告訴小向進行一趟時空旅行最短的路徑。
小向感到非常焦急,要是不能走最短的路徑的話她將會失眠一個月,於是她將這個任務託付給你,天龍國的熱血爆肝工程師。
小向的奇幻旅程就是在幾個時空座標中進行時空穿梭,時空穿梭的距離可以用以下公式求出:
$$ \sqrt{(x_ 1 -x_ 2 )^ 2 +(y_ 1 -y_ 2 )^ 2 } ,其中(x_ 1 ,y_ 1)和(x_ 2,y_ 2)分別是兩個時空座標的位置$$
奇幻旅程必須經過所有的時空座標,也就是說,你必須找出一條路徑,經過所有的時空座標後再回到起點。
請你幫助小向找出奇幻旅程的最短路徑。
第一行有一個整數N,代表總共有N個時空座標。
接下來N行,每行有兩個整數X和Y,代表小向想要去旅行的時空座標,依序編號從1~N。
對於全部的五筆測試資料,
測資1:N=6
測資2:N=11
測資3:N=14
測資4:N=127
測資5:N=127
對於所有的測試資料,$0 \leq X,Y \leq 20000 $
對於一次奇幻旅程,請輸出一行,總共N個正整數,代表小向的奇幻旅程依序經過那些時空座標,並以最短的路徑長度完成旅行。
注意你的路徑並不一定要從某個起點開始,只要記得經過所有的時空座標就可以了。(小向會自己從最後一個時空座標穿梭回起點)
對於測資1~3,你的路徑長度必須是最短的路徑。
對於測資4:小向允許你的路徑長度在最短路徑的500%以內。
對於測資5:小向允許你的路徑長度在最短路徑的120%以內。
小向說,你沒辦法完成全部的奇幻旅程也沒關係,但是她希望你至少試試看最簡單的。
2015建中校隊入隊考試-複試
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 6 |
2 | 1 | 10 |
3 | 2 | 42 |
4 | 3 | 16 |
5 | 4 | 26 |