melkman算法講解？

Melkman 算法使用雙端隊列來實現這個原理，假設雙端隊列為 $D$。所有隊列操作可以用入隊首、出隊首、入隊尾、出隊尾來描述，實際操作過程可以描述為：

假設點集合的坐標可以表示為 $ (x,y) $，那么首先找出 $x$ 值最小的點記為 $P_0$。

然后選定一個方向，比如逆時針方向。然后計算所有剩余的每一個點 $P_0$ 與 $P_x$ 形成的向量 $\overrightarrow{P_0P_x}$ 與 $y$ 軸負方向的夾角。根據向量的點積公式計算出夾角之后根據夾角從小到大就行排序得到有序集合 $S={P_0,P_1,P_2…P_{n-1}}$。

記某一時刻 $D$ 的狀態為：$P_tP_{t-1}…P_0…P_{b-1}P_b$ ，對于 $S$ 中的每一個點進行遍歷：

3.1 如果是 $P_0$ 則首先將 $P_0$ 入隊尾，如果是 $P_1$ 則入隊尾，如果是 $P_2$ 則入隊首并且入隊尾。

3.2 假設遍歷到當前節點 $P_i$ ：

? 3.2.1 如果 $P_{b-1}P_bP_i$ 能保持左轉特性則繼續，否則 $P_b$ 出隊尾，如此往復直到 $P_{b-m-1}P_{b-m}P_i$ 能夠滿足左轉特性，$P_i$ 入隊尾。

? 3.2.2 如果 $P_iP_tP_{t-1}$ 能保持左轉特性則繼續，否則 $P_t$ 出隊首，如此往復直到 $P_iP_{t-n}P_{t-n-1}$ 能夠滿足左轉特性，$P_i$ 入隊首。

返回 $D$。