2008年12月14日 星期日

UVa 109 SCUD Busters

解題策略

典型的凸包 (Convex Hull ) 問題。我是採用 Graham's Scan 來解。作法可以參考維基條目 Graham's Scan,我就是照著條目裡的算法原封不動實做的。

本題要找出所有被飛彈摧毀的王國的國土面積總和。過程中一共有兩件事要解決,第一個要知道每個王國的國土面積,第二個要能判斷飛彈落點有沒有打中王國。

求國土面積,要先對王國內的所有的發電廠位置求凸包,然後由凸包去計算多邊形面積 (題目頁有給多邊形面積公式) 。 判斷飛彈落點是否落在國土內,也是以凸包為基礎,沿著凸包的每個邊判斷,如果飛彈落點都在邊的左側,那就表示打中了!

注意

使用Graham's Scan 時要特別注意共線問題,尤其是起始點三點共線,例如 (0,0) (1,1) (2,2) (1,3) ,求出來的凸包應該是 (0,0) (2,2) (1,3)。

閒聊

@2011.10.07
有點囉嗦的題目。2008年底我第一次解這題,因為過程有點曲折,所以花了好幾天才解出來,而且一直搞不定 std::sort( ) 的判斷函數,現在重寫一遍,感覺比較清爽一些了!