wa1-4可能是因为
查看原帖
wa1-4可能是因为
868672
undefina楼主2024/4/22 16:05

初学闵可夫斯基和,可能有误,轻喷。

这是我WAWA的时候的求凸包代码:

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。

2024/4/22 16:05
加载中...