convex_hull_andrew

Andrew's monotone chain duyệt $n$ điểm đã sắp theo $x$ (ties by $y$) và build lower hull via stack. Với mỗi điểm mới $p$: while top-2 của stack plus $p$ tạo right turn (cross product $\le 0$), pop. Sau đó push $p$. Cross product: $\text{cross}(O, P, Q) = (P_x - O_x)(Q_y - O_y) - (P_y - O_y)(Q_x - O_x)$. Sign $> 0$: left turn (counterclockwise). Sign $< 0$: right turn. Sign $= 0$: collinear.

Process $A(0,1)$. Stack rỗng, không có gì để check. Push $A$.

Process $B(1,0)$. Stack $=[A]$, chỉ 1 phần tử nên không check turn. Push $B$. Vẽ tentative segment $A \to B$.

Process $C(2,2)$. Check triple $(A, B, C)$: $\text{cross}(A,B,C) = (1-0)(2-1) - (0-1)(2-0) = 1 - (-2) = 3 > 0$. Left turn — keep $B$ on the stack.

Push $C$. Stack $=[A, B, C]$. Vẽ tentative segment $B \to C$.

Process $D(3,1)$. Check triple $(B, C, D)$: $\text{cross}(B,C,D) = (2-1)(1-0) - (2-0)(3-1) = 1 - 4 = -3 \le 0$. Right turn — pop $C$ from stack.

$C$ popped. Stack $=[A, B]$. Segment $B \to C$ dimmed (discarded, nhưng giữ trên canvas để author thấy algorithm progression). Now check triple $(A, B, D)$: $\text{cross}(A,B,D) = (1-0)(1-1) - (0-1)(3-0) = 0 - (-3) = 3 > 0$. Left turn — stop popping, push $D$.

Stack $=[A, B, D]$. Vẽ segment $B \to D$.

Process $E(4,3)$. Check triple $(B, D, E)$: $\text{cross}(B,D,E) = (3-1)(3-0) - (1-0)(4-1) = 6 - 3 = 3 > 0$. Left turn — push $E$.

Stack $=[A, B, D, E]$. Vẽ segment $D \to E$.

Process $F(5,0)$. Check triple $(D, E, F)$: $\text{cross}(D,E,F) = (4-3)(0-1) - (3-1)(5-3) = -1 - 4 = -5 \le 0$. Right turn — pop $E$.

$E$ popped. Stack $=[A, B, D]$. Check triple $(B, D, F)$: $\text{cross}(B,D,F) = (3-1)(0-0) - (1-0)(5-1) = 0 - 4 = -4 \le 0$. Right turn again — pop $D$.

$D$ popped. Stack $=[A, B]$. Check triple $(A, B, F)$: $\text{cross}(A,B,F) = (1-0)(0-1) - (0-1)(5-0) = -1 - (-5) = 4 > 0$. Left turn — stop popping, push $F$.

Stack $=[A, B, F]$. Vẽ segment $B \to F$. Hull đang hình thành ở bottom — $A$, $B$, $F$ đều là phần của final hull.

Process $G(6,4)$. Check triple $(B, F, G)$: $\text{cross}(B,F,G) = (5-1)(4-0) - (0-0)(6-1) = 20 - 0 = 20 > 0$. Left turn — push $G$.

Stack $=[A, B, F, G]$. Vẽ segment $F \to G$.

Process $H(7,2)$. Check triple $(F, G, H)$: $\text{cross}(F,G,H) = (6-5)(2-0) - (4-0)(7-5) = 2 - 8 = -6 \le 0$. Right turn — pop $G$.

$G$ popped. Stack $=[A, B, F]$. Check triple $(B, F, H)$: $\text{cross}(B,F,H) = (5-1)(2-0) - (0-0)(7-1) = 8 - 0 = 8 > 0$. Left turn — push $H$.

Stack $=[A, B, F, H]$. Vẽ segment $F \to H$. Lower hull walk done. Final lower hull: $A \to B \to F \to H$.

Lower hull complete. 4 points: $A, B, F, H$. Time complexity: $O(n)$ amortized cho stack walk (mỗi point push tối đa một lần và pop tối đa một lần).

Upper hull: walk tương tự nhưng reverse sorted ($H, G, F, E, D, C, B, A$). Để ngắn gọn, mình skip the walk và show kết quả: upper hull có 3 điểm $H, G, A$. $G(6,4)$ giờ chính thức thuộc hull sau khi được reviewed từ phía upper side — trước đó bị popped ở lower walk vì wrong direction.

Convex hull hoàn chỉnh: 5 đỉnh $\{A, B, F, H, G\}$ theo thứ tự counterclockwise. 3 interior points $\{C, D, E\}$ bị pop trong quá trình walk. Total complexity: $O(n \log n)$ cho sort + $O(n)$ amortized cho hai stack walks.

Hull as filled polygon. Thuật toán Andrew's monotone chain ngắn gọn hơn Graham scan (không cần sort theo angle, không cần pivot) và robust với collinear points (chỉ cần thay $\le$ bằng $<$ trong cross-product check nếu muốn giữ collinear points trên hull).