1498| 0
|
[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長。 考慮形式B: 如A一樣的方法做圓,會發現一樣無法覆蓋凸包,這也不可能。 所以唯一的可能就是第三種:頂點-頂點。 做凸包的方法有很多種,這裡使用的是極角排序+Graham's Scan,完成凸包後再做旋轉卡殼,繞出最遠的端點,再取最大值即可。 時間複雜度分析:
總時間複雜度:[tex]O(nlogn)[/tex] 爽電其他解法,慶祝拿下TopCoder!
購買主題
本主題需向作者支付 20 枚金幣 才能瀏覽
| |