关于斜率优化中凸包的各种维护方式的疑惑?
  • 板块P4983 忘情
  • 楼主E_huanJX泛舟客
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/12/8 22:07
  • 上次更新2023/10/27 00:05:48
查看原帖
关于斜率优化中凸包的各种维护方式的疑惑?
546246
E_huanJX泛舟客楼主2022/12/8 22:07

众所周知斜率优化中维护凸包可以通过直接求斜率、把斜率式转化成乘积式、叉积......但是有时候会碰到只有其中一种可以,而基本等价的形式不可以的情况,感觉挺困扰的。(但困扰的时候都没问出来,现在找不到代码了)。刚好看到这个,两份代码只有维护凸包的一行不一样,一个是直接求斜率可以 AC,一个是把斜率式的分母乘到另外一边转化成乘积式(且用了 double__int128 都不行)会 WA 在第二个样例,又激发了我的疑惑,乘积式难道不应该更精确吗?想向神犇们求教!!

某些题目中维护凸包的多种方式只有其中一种可以 AC,而基本等价的形式 WA 的情况是什么原因呢?

!!!拜谢!!!

2022/12/8 22:07
加载中...