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( ) 的判斷函數，現在重寫一遍，感覺比較清爽一些了!