凸包
Andrew算法
- x，y从小到大排序
- 正向做一遍，反向做一遍，用栈维护
- 如果栈顶向量与当前点围成的面积为负，则弹出
- 凸包的点为逆时针
cpp
int stk[N],top;
bool used[N];
vector<Point> andrew(vector<Point> &q){
sort(q.begin(),q.end());
int n=q.size();
top=0;
for(int i=0;i<n;i++)used[i]=false;
for(int i=0;i<n;i++){
while(top>=2&&sign(area(q[stk[top-1]],q[stk[top]],q[i]))<=0){
if(sign(area(q[stk[top-1]],q[stk[top]],q[i])<0))used[stk[top--]]=false;
else top--;
}
stk[++top]=i;
used[i]=true;
}
used[0]=false;
for(int i=n-1;i>=0;i--){
if(used[i])continue;
while(top>=2&&sign(area(q[stk[top-1]],q[stk[top]],q[i]))<=0)top--;
stk[++top]=i;
}
vector<Point> hull;
for(int i=1;i<top;i++)hull.push_back(q[stk[i]]);
return hull;
}