CodeForces Contest #70 D

題目要求 maintain 一 set 點的 convex hull, 有 2 種 operation:
1. add(x): 把 x 加進 S 中
2. query(x): 問 x 是否在 S 的 convex hull 內



如果一點在 convex hull中, 以後都會在 convex hull中
具題做法是, 先找一點 convex hull 內的點 (我用的是最初 3 點的 CG), 以該點為 pivot point P

然後用一個 set 去 store 住 convex hull 上的點, key 是與 P 的 polar angle
對於新的點 x, 先找 x 在 S 中的左右兩點, 用 cross product 便可判斷是否在 convex hull 中

如果要把 x 加進 S 中, 先判斷 x 是否在 convex hull中, 如果不是, 只要對 x 左面和右面不斷 erase 形成反角的點 ; 否則 convex hull 不會改變



容易錯的地方
1. 兩點一樣的點 (以為題目說 input 沒有 2 點重覆, 原來只是保證 convex hull 沒有)
2. polar angle 相同
3. 和上面兩點有關, 就是在 set 中 insert(x), 但原來 x 已經存在, 之後 erase(x) 會把原本的點都刪埋
4. add(x) 前沒有 check x 是否在 convex hull 中