题目数据弱
查看原帖
题目数据弱
761114
yyym楼主2024/8/15 21:33

给出两个旋转卡壳部分的关键部分代码:

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]]) });
    }

两份代码唯一的不同在于变量 jj 的初始化值不同, 第一份代码是错误的, 第二份代码是正确的, 但是两份代码都可以通过该题。

我们可以用下面这个数据来验证, 这是2024年牛客多校第九场H题的部分数据:

9
-19 6
-14 -16
-12 -20
6 -20
15 -18
20 -8
20 -1
11 14
-19 18

可以发现两份代码的输出不一样。

2024/8/15 21:33
加载中...