关于枚举边时扫描的一点疑问
查看原帖
关于枚举边时扫描的一点疑问
208881
Bitter_楼主2022/5/25 23:44

写代码的时候 发现直接按照题解上面写似乎会导致数组越界访问到零向量,也就是说,这份代码是 AC 的:

其中 cv 是凸包数组,clen 是数组长度,Cper 是计算的函数,^ 运算是重载的叉积

db Cper() {
	if(clen == 2) return fdis(cv[0], cv[1]);
	cv[clen++] = cv[0];
	int j = 2;
	db ans = 0;
	for(int i = 0; i < clen; ++i) {
		while(((cv[i + 1] - cv[i]) ^ (cv[j] - cv[i])) < ((cv[i + 1] - cv[i]) ^ (cv[(j + 1) ] - cv[i]))) j = (j + 1) % clen;
		ans = Max(ans, Max(fdis(cv[j], cv[i]), fdis(cv[j],cv[i + 1])));
	}
	return ans;
}

但是这样会访问到类似 j+1=clen,i+1=clenj + 1 = clen , i + 1 = clen 这样的空点,于是我改成了这样:

db Cper() {
	if(clen == 2) return fdis(cv[0], cv[1]);
	cv[clen++] = cv[0];
	int j = 2;
	db ans = 0;
	for(int i = 0; i < clen; ++i) {
		while(((cv[(i + 1) % clen] - cv[i]) ^ (cv[j] - cv[i])) < ((cv[(i + 1) % clen] - cv[i]) ^ (cv[(j + 1) % clen] - cv[i]))) j = (j + 1) % clen;
		ans = Max(ans, Max(fdis(cv[j], cv[i]), fdis(cv[j],cv[(i + 1) % clen])));
	}
	return ans;
}

它却在第 11 个点 WA 掉了,答案偏小,求大佬指教。

2022/5/25 23:44
加载中...