给出两个旋转卡壳部分的关键部分代码:
for(int i = 1, j = 1; i <= top ; i ++) {
PT Line = arr[sta[i]] - arr[sta[i + 1]];
while ( Line.cross(arr[sta[i]] - arr[sta[j % top + 1]]) > Line.cross(arr[sta[i]] - arr[sta[j]]) ) {
j = j % top + 1;
}
ans = max({ans, arr[sta[j]].dis2(arr[sta[i]]), arr[sta[j]].dis2(arr[sta[i + 1]]) });
}
for(int i = 1, j = 2; i <= top ; i ++) {
PT Line = arr[sta[i]] - arr[sta[i + 1]];
while ( Line.cross(arr[sta[i]] - arr[sta[j % top + 1]]) > Line.cross(arr[sta[i]] - arr[sta[j]]) ) {
j = j % top + 1;
}
ans = max({ans, arr[sta[j]].dis2(arr[sta[i]]), arr[sta[j]].dis2(arr[sta[i + 1]]) });
}
两份代码唯一的不同在于变量 j 的初始化值不同, 第一份代码是错误的, 第二份代码是正确的, 但是两份代码都可以通过该题。
我们可以用下面这个数据来验证, 这是2024年牛客多校第九场H题的部分数据:
9
-19 6
-14 -16
-12 -20
6 -20
15 -18
20 -8
20 -1
11 14
-19 18
可以发现两份代码的输出不一样。