求凸包

算法步骤

• 将点排序：x为第一关键字，y为第二关键字

• 从左向右维护上半部分，从右向左维护下半部分。用单调栈维护。如果下一条边在栈顶元素的左侧，删去栈顶元素；下一条边在栈顶元素的右侧，就不删除栈顶元素。相等的话取决题目要求。

• 最后记得用起点(栈底元素)更新一遍，边界点。

求半平面交

保留每条直线的左侧部分
算法步骤

• 将向量按照角度排序 $atan2(y,x)$

• 按顺序从左向右扫描所有向量，用双端队列维护半平面交的轮廓。

• 队尾或队头在当前向量的右侧时，删去队头或队尾

• 双端队列的队尾更新队头，队头更新队尾.