查看: 686|回復: 0

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

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-2-12 11:21
  • 簽到天數: 2 天

    [LV.1]初來乍到

    18

    主題

    31

    帖子

    211

    積分

    好好學生

    Rank: 3Rank: 3

    積分
    211
    發表於 2014-9-27 17:09:29 | 顯示全部樓層 |閱讀模式
    原題: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

    case1


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

    case2

    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

    topcoder1105


    購買主題 本主題需向作者支付 20 枚金幣 才能瀏覽
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表