TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

55.6% (5/9)

Submission's AC Ratio

10.8% (11/102)

Tags

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 1

4
1 2
2 1
2 3
3 2

Sample Output 1

2 4 3 1

Hints

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

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 6
2 1 10
3 2 42
4 3 16
5 4 26

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5