TopCoder

User's AC Ratio

54.2% (26/48)

Submission's AC Ratio

12.2% (61/498)

Tags

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 1

4
0 0
0 8
8 0
8 8

Sample Output 1

0 3

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0~4 11
2 0~8 14
3 0~11 22
4 0~15 53

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 32768 262144 1 2 3 4
1 900 32768 262144 1 2 3 4
2 900 32768 262144 1 2 3 4
3 900 32768 262144 1 2 3 4
4 900 32768 262144 1 2 3 4
5 1500 32768 262144 2 3 4
6 1500 32768 262144 2 3 4
7 1500 32768 262144 2 3 4
8 1500 32768 262144 2 3 4
9 900 32768 262144 3 4
10 900 32768 262144 3 4
11 900 32768 262144 3 4
12 1300 32768 262144 4
13 1350 32768 262144 4
14 1500 32768 262144 4
15 1450 32768 262144 4