logo标签列表

什么是凸包技巧？

algorithmdynamic-programming
5
我在解决来自codeforces.ru的问题时，遇到了一个无法解决的问题，编者按建议使用凸包技巧。
我尝试阅读这篇 关于凸包技巧的文章 ，但没有理解它。
有人能告诉我什么是凸包技巧吗？
提前感谢。
2个回答
6
如果您有一组线 Yi = Ai * X + Bi，那么问题就是找到给定 X 的最小 Yi。天真地说，您可以尝试评估此 X 的所有 Yi 并选择最小的一个。但是，如果您想为一系列 X 值评估值，那么您可以更好地确定 Yi 相交的位置，然后对于每个相交之间的间隔确定哪个 Yi 是最小的。然后，给定一个 X，您选择相应的间隔，并仅评估该间隔上最小的 Yi。
（在这里用绿色线条可视化：http://wcipeg.com/wiki/File:Convex_hull_trick1.png）
0
假设我们有M条线。给定任意点x，M条线按照y(x)值的某种顺序排列。直到发生某个交点为止，线的顺序保持不变，此时2条线的顺序总是被交换。
知道了扫描X轴并对每个交点的线条顺序进行排序，然后你就得到了数据结构，该结构为你提供了X轴上每个区间（从一个交点到另一个交点）的线条顺序。就是这样...
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接