什么是Convex船体技巧？

Question

我是从codeforces.ru解决问题,但我无法解决问题和社论说(http://codeforces.com/blog/entry/7785)使用凸壳技巧.

我试着阅读这篇关于凸壳技巧(wcipeg.com/wiki/Convex_hull_trick)的文章,但无法理解.

任何人都可以告诉我究竟什么是凸壳技巧？

提前致谢.

Answer 1

如果你有一组线Y _i = A _i*X + B _i,那么问题是找到给定X 的最小Y _i.天然,你可以尝试评估这个X的所有Y _i并选择最小的一个.但是,如果要评估X的一系列值,则可以更好地确定Y _i相交的位置,然后对于交叉点之间的每个间隔确定哪个Y _i最小.然后,给定一个X,您可以选择相应的间隔,并仅评估该间隔中最小的Y _i.

(由绿线可视化:http://wcipeg.com/wiki/File:Confve_hull_trick1.png)