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 中

POJ 2986 - A Triangle and a Circle

要搵一個三角形的一個圓形 intersection 的面積

做法: 對於三角形ABC 和圓C, union的面積 = [ABO ∩ C] + [BCO ∩ C] + [CAO ∩ C] (signed area)
而每一次計圓心三角形的 intersection 可分為4個case

另外, 使用 asin 和 acos 時, 應該 handle asin(1.00000..001) 的情況

URAL 1043 - Cover an Arc

First, find the center and the radius of the circle.
Since we are looking for a bounding rectangle, we need to calculate minX, maxX, minY, maxY.

Intuition: Just compare with the up-most, leftmost, rightmost and the down-most point of the circle!
Next, we have to determine whether a point on a circle is on an arc.

Arrange the two ends of the arc A,B such that A->B is clockwise.
To check whether P is on the arc, just see whether triangle APB is clockwise or not, which can be easily done by cross product.

Last Bug:

mnx = (int)(mnx+1e-10);
mny = (int)(mny+1e-10);
mxx = ceil(mxx-1e-10);
mxy = ceil(mxy-1e-10);

Correct version:

mnx = floor(mnx+1e-10);
mny = floor(mny+1e-10);
mxx = ceil(mxx-1e-10);
mxy = ceil(mxy-1e-10);

Incorrect version won't work with negative numbers..

POJ 2826 - An Easy Problem?!

A geometry problem. Not complex, but need to be careful and it is easy to miss some cases.

First, there are some conditions that the answer will be 0.00
1. Either one segment is horizontal
2. The segments have no intersection
3. The segments are parallel

If the segments passed those cases, then find the intersection point P of the segments.
The area will be a triangle.



However, there are one more case that needed to be consider.