[UVA] 109 SCUD Busters

Convex Hull的經典題目。在一個二維的世界上，一個國家的國境是由一堆村莊組成的convex hull定義的。如果飛彈落在國境內，那就把國土面積累加到總焦土面積上。

題目本身沒有什麼陷阱，主要是練習computation geometry的幾個topic:

1. 給定一堆座標，求出convex hull
演算法筆記有非常細盡的介紹。我認為 Andrew's Monotone Chain 是最易懂，最好實作，完義不用考慮共線等boundary condition，效率也不差的作法。建議搭配wiki的pseudo code，理解這個方法的精髓。自己練習一下，

2. 求出convex hull 的面積
題目有給出公式。這裡有簡易的證明。

3. 判斷一個點是否落在一個convex hull裡面
我使用 equal area的作法。把convex hull的每個頂點跟測試點連起來，這樣會把convex hull分成n個小三角形。把所有小三角的面積相加，看是否等於convex hull的面積。相等即在內，反之在外。

另一個作法是sum angle, 即看看測試點與任二相鄰頂點的夾角總合是否為180度。是的話就在內。不過算角度要用除法，相比面積比較，可能會有floating precision的問題。