我正在从 codeforces.ru 解决问题，但我无法解决问题，社论说使用凸包技巧。
我试图阅读这篇关于凸包技巧的文章，但无法理解。
谁能告诉我究竟什么是凸包技巧？
提前致谢。
问问题
5808 次
2 回答
5
如果你有一组线 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:Convex_hull_trick1.png ）
于 2013-07-24T13:29:01.607 回答
0
假设我们有 M 行。给定任何点 x，M 行在 y(x) 值方面按某种顺序排列。线的顺序被保留，直到某个交点出现，其中 2 条线的顺序总是被交换。
知道扫描 X 轴并将每个交点的线顺序排序到另一个，然后您将获得数据结构，该结构为您提供 X 轴上每个间隔（从一个交点到另一个）的线顺序。而已...
于 2015-09-11T10:03:35.813 回答