melkman算法讲解

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$。