TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

12.5% (12/96)

Description

還記得小向嗎?對,就是那個天龍國的天才魔法少女。
身為天龍國的天才魔法少女,在時空中穿梭是一定要的,小向常常使用她的神奇魔法到處旅行。
有天,小向突然很想要進行時空穿梭,她決定要從她所在的位置開始她的奇幻旅程。

這時候問題就來了,
我們都知道,時空旅行其實就是一個在時間和空間組成的二維平面座標上面旅行(橫軸是時間,縱軸是空間),小向使用她的魔法算出了她的幾個想要旅行的時空座標,並且將她標示在魔法導航器上,但是這個魔法導航器只能算出兩點間的時空距離,卻不能告訴小向進行一趟時空旅行最短的路徑。
小向感到非常焦急,要是不能走最短的路徑的話她將會失眠一個月,於是她將這個任務託付給你,天龍國的熱血爆肝工程師。

小向的奇幻旅程就是在幾個時空座標中進行時空穿梭,時空穿梭的距離可以用以下公式求出:
$$ \sqrt{(x_ 1 -x_ 2 )^ 2 +(y_ 1 -y_ 2 )^ 2 } ,其中(x_ 1 ,y_ 1)和(x_ 2,y_ 2)分別是兩個時空座標的位置$$
奇幻旅程必須經過所有的時空座標,也就是說,你必須找出一條路徑,經過所有的時空座標後再回到起點。
請你幫助小向找出奇幻旅程的最短路徑。

Input Format

第一行有一個整數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 $

Output Format

對於一次奇幻旅程,請輸出一行,總共N個正整數,代表小向的奇幻旅程依序經過那些時空座標,並以最短的路徑長度完成旅行。
注意你的路徑並不一定要從某個起點開始,只要記得經過所有的時空座標就可以了。(小向會自己從最後一個時空座標穿梭回起點)

對於測資1~3,你的路徑長度必須是最短的路徑。
對於測資4:小向允許你的路徑長度在最短路徑的500%以內。
對於測資5:小向允許你的路徑長度在最短路徑的120%以內。

Sample Input

4
1 2
2 1
2 3
3 2

Sample Output

2 4 3 1

Hints

小向說,你沒辦法完成全部的奇幻旅程也沒關係,但是她希望你至少試試看最簡單的。

Problem Source

2015建中校隊入隊考試-複試

Subtasks

For Testdata: 0 ~ 0, Score: 6
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 42
For Testdata: 3 ~ 3, Score: 16
For Testdata: 4 ~ 4, Score: 26
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144