大草履蟲(學名:Paramecium caudatum),是一種纖毛蟲,其身體呈圓筒形,前端較圓,中後部較寬,後端較尖,平面看形狀像倒置的草鞋。
某隻家財$i$貫的大草履蟲,擁有一間很大的房子。為了適應牠的外型,這間房子俯視來看可以視為一個凸$N$邊形(如果有凹點的話會刺傷草履蟲),而每一個轉折點都稱為一個「角落」。但有一天,牠讀了《祭枯乾草履蟲弔文》,大受感動,體認到茫茫大海中可能有許多的草履蟲無家可歸,因此他決定要把自己的房子低價出租給其他草履蟲們使用。
為了保持原先建築設計的美感以及居住環境的安寧,草履蟲決定要興建幾道牆作為隔間,並且要求下列幾件事情:
一、每一道牆都是直的,且由某個角落連接到另一個不相鄰的角落(牆的厚度可以忽略)。
二、任兩道牆不會在中途相交。
三、由這些牆隔出的每一個房間都是個三角形。
雖然草履蟲很有錢,但興建牆要花許多時間,興建的牆的總長如果是$P$,草履蟲要花$P$分鐘的時間才能蓋完。請你給出一種符合草履蟲要求的條件的興建方案,使得草履蟲蓋牆所要花的時間最少。
第一行有一個正整數$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 |
輸出$K$行代表草履蟲應該興建$K$道牆。每行有兩個正整數$A_i, B_i$,代表要興建的第$i$道牆要連接$A_i$和第$B_i$個角落。如果最佳方案的興建時間是$Q$,你的興建方案所花的時間只要在$(1+\frac{1}{10^ {10}})Q$以內都會被接受。
Problem set / Description by Yihda Yol
建國中學105學年度校內第六次模擬賽pA
題目改編自TOI2015初選pE
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 11 |
2 | 0~8 | 14 |
3 | 0~11 | 22 |
4 | 0~15 | 53 |