本人学艺不精,想问一个问题:
旋转卡壳为什么必须枚举边和对踵点,而不是直接没法枚举两个点之间的距离。
就比如 模板题:
正确做法
for(int i = 1, j = 2; i <= cnt; ++ i)
{
while(sign(cross(q[j] - q[i], q[j] - q[i + 1]) - cross(q[j + 1] - q[i], q[j + 1] - q[i + 1])) < 0)
j = j % cnt + 1;
ans = max(ans, max(dot(q[i] - q[j], q[i] - q[j]), dot(q[i + 1] - q[j], q[i + 1] - q[j])));
}
错误 92pts 但不知道为什么错的部分
for(int i = 1, j = 2; i <= cnt; ++ i)
{
while(sign(dot(q[i] - q[j], q[i] - q[j]) - dot(q[i] - q[j + 1], q[i] - q[j + 1])) < 0)
j = j % cnt + 1;
ans = max(ans, dot(q[i] - q[j], q[i] - q[j]));
}
其中,sign 解决精度比较问题,q[i] 是凸包点集,dot 是点积,最后得到的答案为 ans。
就是不知道为什么会错,是两个点的距离不满足单调性吗,还是怎么。也找不到 hack 数据,求奆佬解答。