TopCoder

User's AC Ratio

52.9% (27/51)

Submission's AC Ratio

11.9% (62/522)

Tags

Description

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

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

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

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

Input Format

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

對於所有測資,4N800;|xi|,|yi|3×104

子任務(測資) 額外限制 分數
1 (0~4) N9 11
2 (0~8) N17 14
3 (0~11) N100 22
4 (0~15) 53

Output Format

輸出K行代表草履蟲應該興建K道牆。每行有兩個正整數Ai,Bi,代表要興建的第i道牆要連接Ai和第Bi個角落。如果最佳方案的興建時間是Q,你的興建方案所花的時間只要在(1+11010)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