关于旋转卡壳的一点疑惑
  • 板块学术版
  • 楼主Fated_Shadow
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/12/21 19:45
  • 上次更新2023/12/21 22:26:26
查看原帖
关于旋转卡壳的一点疑惑
622466
Fated_Shadow楼主2023/12/21 19:45

本人学艺不精,想问一个问题:
旋转卡壳为什么必须枚举边和对踵点,而不是直接没法枚举两个点之间的距离。
就比如 模板题:

正确做法

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 数据,求奆佬解答。

2023/12/21 19:45
加载中...