TopCoder

Thumb rezero
Re Zero
Re Zero

User's AC Ratio

37.5% (6/16)

Submission's AC Ratio

7.7% (7/91)

Description

大草履蟲(學名:Paramecium caudatum),是一種纖毛蟲,其身體呈圓筒形,前端較圓,中後部較寬,後端較尖,平面看形狀像倒置的草鞋。

某隻家財$i$貫的大草履蟲,擁有一間很大的房子。為了適應牠的外型,這間房子俯視來看可以視為一個凸$N$邊形(如果有凹點的話會刺傷草履蟲),而每一個轉折點都稱為一個「角落」。但有一天,牠讀了《祭枯乾草履蟲弔文》,大受感動,體認到茫茫大海中可能有許多的草履蟲無家可歸,因此他決定要把自己的房子低價出租給其他草履蟲們使用。

為了保持原先建築設計的美感以及居住環境的安寧,草履蟲決定要興建幾道牆作為隔間,並且要求下列幾件事情:
一、每一道牆都是直的,且由某個角落連接到另一個不相鄰的角落(牆的厚度可以忽略)。
二、任兩道牆不會在中途相交。
三、由這些牆隔出的每一個房間都是個三角形。

雖然草履蟲很有錢,但興建牆要花許多時間,興建的牆的總長如果是$P$,草履蟲要花$P$分鐘的時間才能蓋完。請你給出一種符合草履蟲要求的條件的興建方案,使得草履蟲蓋牆所要花的時間最少。

Input Format

第一行有一個正整數$N$,代表草履蟲房間的形狀是一個凸$N$邊形。
接下來有$N$行,每行有兩個整數$x_i, y_i$,代表第$i$個角落的座標是$(x_i,y_i)$。不會有兩個角落在相同的位置。
角落們已經按照$(x,y)$數對的字典序遞增排序。

對於所有測資,$4\leq N\leq 800; |x_i|, |y_i|\leq 3\times 10^ 4$。

子任務(測資) 額外限制 分數
1 (0~4) $N \leq 9$ 11
2 (0~8) $N\leq 17$ 14
3 (0~11) $N\leq 100$ 22
4 (0~15) 53

Output Format

輸出$K$行代表草履蟲應該興建$K$道牆。每行有兩個正整數$A_i, B_i$,代表要興建的第$i$道牆要連接$A_i$和第$B_i$個角落。如果最佳方案的興建時間是$Q$,你的興建方案所花的時間只要在$(1+\frac{1}{10^ {10}})Q$以內都會被接受。

Sample Input

4
0 0
0 8
8 0
8 8

Sample Output

0 3

Hints

Problem Source

Problem set / Description by Yihda Yol
建國中學105學年度校內第六次模擬賽pA
題目改編自TOI2015初選pE

Subtasks

For Testdata: 0 ~ 4, Score: 11
For Testdata: 0 ~ 8, Score: 14
For Testdata: 0 ~ 11, Score: 22
For Testdata: 0 ~ 15, Score: 53
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 900 32768 262144
1 900 32768 262144
2 900 32768 262144
3 900 32768 262144
4 900 32768 262144
5 1500 32768 262144
6 1500 32768 262144
7 1500 32768 262144
8 1500 32768 262144
9 900 32768 262144
10 900 32768 262144
11 900 32768 262144
12 1300 32768 262144
13 1350 32768 262144
14 1500 32768 262144
15 1450 32768 262144