在判断处理删除队尾点的时候(以下凸包为例),有下面两种写法:
写法 1:
while(head<tail&&slope(q[tail],q[tail-1])>=slope(i,q[tail]))
--tail;
写法 2:
while(head<tail&&slope(q[tail],q[tail-1])>=slope(i,q[tail-1]))
--tail;
(这里的 slope 是求斜率的自定义函数,q 是队列,head 和 tail 分别为队头和队尾)
按道理来说,感觉两种都可以啊,而且画了大半天图,都没能想出反例(有可能是我太菜了)。
对于 [HNOI2008] 玩具装箱 这题,两种写法都可以过去,但是在 百日旅行 这题的斜率优化做法中写法 2 不能过掉所有的数据。
本校大佬持很多不同观点,还有巨佬表示是精度问题(不知道是否正确)。
求对于写法 2 错误性的证明或推倒qwq。