初学闵可夫斯基和,可能有误,轻喷。
这是我WA的时候的求凸包代码:
int andrew(point *p,int n){
sort(p+1,p+1+n);
int top=0;
for(int i=1;i<=n;++i){
while(top>=2 && ((sta[top]-sta[top-1])^(p[i]-sta[top-1]))<=0) top--;
sta[++top]=p[i];
}
int k=top;
for(int i=n-1;i>=1;--i){
while(top>k && ((sta[top]-sta[top-1])^(p[i]-sta[top-1]))<=0) top--;
sta[++top]=p[i];
}
if(n>1) top--;
return top;
}
if(n>1) top--的目的是防止把第一个点算两遍。但是如果有这句话,之后求闵可夫斯基和的时候可能就不会考虑到第n个点到第1个点这条边,然后出锅了。
把这句话删掉然后套一个正确的判断点在凸包内的模板即可AC。