最小的圍欄長度


Submit solution

分數: 100 (partial)
時間限制: 1.0s
記憶體限制: 1G

作者:
題目類型
允許的語言
Assembly, Brainfuck, C, C++, Python

在電電家隔壁鄰居的後院地上有一些木樁,電電實在覺得有點礙眼,所以就有股衝動很想把他拆掉,於是每次放學經過那邊的時候就會情不自禁地把它拆掉幾根,令鄰居非常頭痛,所以鄰居想到一個好方法:就是在所有木樁中選一些當作支點圍成一個圍欄包住所有其他的木樁,因為圍欄很高而且又堅固,這樣電電就沒有辦法再拔掉任何木樁了。只是他們還需要考慮一下成本,如果圍欄長度越長,價格就越高,於是鄰居請你來幫忙了!希望你可以寫一個程式判斷能圍住所有木樁的最小圍欄長度。

輸入格式

第一行有一個整數 \(N\) (\( N <= 100000 \)),表示有多少木樁。 接下來有 \(N\) 行,每行有 \(2\) 個整數 \(x,y\) ,表示有一個位於 \((x,y)\) 的木樁 (\( -10000 ≤ x,t ≤ 10000 \)) 保證所有木樁不會在同一條直線上,而且一個位置只有一個木樁。

輸出格式

輸出最小長度,小數點取至第 \(2\) 位。

範例輸入

["5\r\n1 1\r\n2 2\r\n2 1\r\n1 3\r\n0 0","10\r\n0 0\r\n3 7\r\n6 3\r\n3 3\r\n9 7\r\n7 3\r\n7 1\r\n5 5\r\n7 7\r\n2 1"]

範例輸出

["7.81","27.01"]

評論

目前沒有評論。