凸包学习笔记
凸包，是指能包含点集中所有点的最小凸多边形（三维就是凸多面体）。显然，凸包的所有顶点都是点集中的点。凸包通常有两种出题套路，分别是计算几何（直接求有关凸包的信息）和决策单调性（类似于斜率优化 dp）。由于凸包本身并不好维护且不一定全都用得上，在信息学竞赛中，通常维护上凸壳或下凸壳。凸包可以有这两个凸壳拼接而得。下图是一只可爱的凸包：该图中，红线围起的多边形为凸包，蓝色点与其连线为上凸壳，绿色点与其连线为下凸壳。
一、凸包构建方法
注：该版块内容仅讨论上凸壳。
1.静态构建
首先，我们按照 \(x\) 轴坐标进行排序，然后按顺序一个一个插入点。
我们假设一条线段也是凸壳，那么我们先将前两个点加入上凸壳，然后考虑拓展这个上凸壳：
[*]斜率减小
下图就是一个斜率减小的例子：
此时，若采用绿色线段的模式，将第二个蓝色点扔出上凸壳，显然不符合凸包包含所有点的要求，所以直接加入黑点即可。同时，根据这一事实，我们也可以推断出：上凸壳每条边斜率递减。相对应的，下凸壳每条边斜率递增。
[*]斜率增大
下图就是一个斜率增大的例子：
我们发现，假如我们采取红色折线的模式，那么这个凸包就不是一个凸多边形了，所以要将第二个橘色点扔出上凸壳。同时要注意的是，假如仍然保留第一个橘色点，这个凸包也不是一个多边形，所以第一个橘色点也要舍去。说明在舍去一个点后，对于此时凸包最右侧的点是否保留，需要继续递归处理，直至上凸壳只剩两个点。
根据上述讨论，我们总结出了上凸壳的构建方式：
[*]对所有点根据 \(x\) 坐标值进行升序排序。
[*]直接加入前两个点。
[*]将当前第二靠右的点 \(a\)，第一靠右的点 \(b\) 和当前枚举点 \(c\) 进行比较：
[*]若当前上凸壳中点数为 \(1\)，跳出循环；
[*]当线段 \((a,b)\) 的斜率大于线段 \((b,c)\) 的斜率时，直接加入点 \(c\)，跳出循环；
[*]否则弹出 \(b\)，继续循环。
这和单调栈如出一辙。时间复杂度瓶颈为排序，因此时间复杂度为 \(O(n\log n)\)，单调栈部分则为 \(O(n)\)。假如要求时间复杂度非均摊，我们可以用二分找出进行完 \(3\) 操作后的栈顶，单次时间复杂度为 \(O(\log n)\)（这类题有 购票）。
//单调栈法#define dx(x,y) (xc-xc)#define dy(x,y) (yc-yc)int n,xc,yc,id,st,tp;int check(int x,int y,int z){ return dx(z,y)*dy(y,x)-\dfrac xy\]
我们发现，假如我们将 \((a_i,b_i)\) 看作坐标系上的点，那么 \(\dfrac{b_i-b_j}{a_i-a_j}\) 相当于两点斜率：当斜率 \(>-\dfrac xy\) 时，\(a_i\) 大的更优；反之，\(a_i\) 小的更优。
这个时候，我们就会发现：假如我们建立所有点的上凸壳，那么无论任何时候，答案都在这个上凸壳上面。查询答案时，我们对上凸壳进行二分即可。当然，这都是 \(y>0\) 的情况，假如 \(y\le 0\)，那我们就需要在下凸壳上二分了。
本题有区间查询，所以可以使用线段树套凸壳的方式进行维护。本题还涉及到一个小小的 \(trick\)：当加入的点在末尾时，我们可以在一个区间被填满后再进行凸壳的建立，因为在加入最后一个点前，这个区间不可能被访问到。
综上，凸壳解决单调性问题的基本套路为：找到点的形式，判断上、下凸壳，选择数据结构。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]