[TIOJ] [凸包][旋轉卡殼][NPSC2006]1105 - H.PS3

原題：http://tioj.ck.tp.edu.tw/problems/1105
測試結果：http://tioj.ck.tp.edu.tw/submissions/2902

早知道用兩個for迴圈也可過這題就好了...... 來介紹一下我的解法吧！

很清楚的，本題是要找尋平面上最遠的兩個點，我們可以證明這兩個點會位於凸包頂點上：

• 因為是凸包所以所有點要嘛在凸包頂點上，要嘛在凸包裡面，我們不討論在邊上的，不過顯然的邊上的頂點不會是最佳解。
• 最遠的兩點只會有三種型式：
  

• 裡面-裡面
• 頂點-裡面
• 頂點-頂點
  

考慮形式A：
若兩點分別為A、B，做以AB為直徑的圓O。因為AB在凸包內，故該圓無法完全包覆凸包，所以答案不會是這種形式，比如說做AB之延長線交凸包於兩點所形成的線段就比AB長。

case1

考慮形式B：
如A一樣的方法做圓，會發現一樣無法覆蓋凸包，這也不可能。

case2

所以唯一的可能就是第三種：頂點-頂點。


做凸包的方法有很多種，這裡使用的是極角排序+Graham's Scan，完成凸包後再做旋轉卡殼，繞出最遠的端點，再取最大值即可。

時間複雜度分析：

• 極角排序：[tex]O(nlogn)[/tex]
• Graham's Scan：[tex]O(n)[/tex] (均攤)
• 旋轉卡殼：[tex]O(n)[/tex](均攤)
  

總時間複雜度：[tex]O(nlogn)[/tex]


爽電其他解法，慶祝拿下TopCoder!

topcoder1105