凸包知识介绍

一、凸包的定义

给定二维平面上的一堆点中，凸包就是将最外层的点连接起来构成的凸多边形，它能包含 点集 中所有的点。

如上图所示，点集中外层的点构成的凸多边形就构成了能够包含所有点的凸包，其中连接相邻顶点构成的边越来越平缓，或者说斜率越来越小构成的一组点叫做上凸壳，而相邻的边，斜率越来越大的一组点叫做下凸壳。

关于斜率，同学们可以认为是直线与横轴在第一象限的夹角，夹角越小，斜率越小，夹角越大，斜率越大，换句话说：斜率越小，越贴近x轴，斜率越大，越贴近y轴。

如图所示，开始只有顶点\(A、B\)构成的凸包，然后加入第三点\(C_1\)，显然\(BC_1\)的斜率是高于\(AB\)的，因此\(AB\)，\(BC_1\)构成了一个下凸壳；
但是如果新加的点不是\(C_1\)而是\(C_2\)，\(BC_2\)的斜率小于\(AB\)，那么\(AB\)和\(BC2\)就不能构成下凸壳了，因为不能作为点集的下边界，不能包含在\(AB\)下面却在\(AC_2\)上面的点，(这样就不是凸包，而是凹包了！)

因此，加入\(C_2\)后，\(AC_2\)将成为下凸壳新的边界了。对于平面上的三点\(A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)\)，(其中\(x_1 < x_2 < x_3,y_1 < y_2 < y_3\)),\(AB\)的斜率小于\(BC_1\)的斜率才能使得\(AB\)、\(BC_1\)形成下凸壳。

二、凸包用途

以本节的三道题为例，写一下我对凸包在此专题中的作用：

此处模拟了一条斜率为\(k\)的直线，上面的点集是它的前序依赖值，问我们，当此直线方程取前序依赖值集中的哪一个点，使得直线方程的截距最小。

答案显而易见，就是从下到上遇到的第一个斜率比自己高的那个点。

非常幸运的是，凸包的维护，也是要求每两个点组成的直线，斜率不断长大，才是下凸壳。换句话说，如果我们用一个单调队列维护了一个凸包的话，那么，在这个集合中通过二分查找，很容易能够找到比当前直线斜率高的第一个点，从而求出此直线方程的截距最小值。

整理一下：

1、我们从小到大，不断的向二维空间中增加一些符合直线方程的点，并动态维护好一个凸包（单调队列）。

2、当新的点想要加入时，它需要找出它的前序点中截距最小的点，可以利用二分搜索在凸包队列中快速找出。

3、我们只要维护好凸包，永远都在下凸壳的组成点集中查找，其它点都肯定不是答案，这样明显提速。再加上面2中提到的单调性+二分，速度杠杠滴~

三、凸包的实现

1、出队列头

我们遍历\(i\)的时候，相当于不断的往点集中加点，并且更新凸包，在求\(f[i]\)时，只需要找到凸包中第一个大于\(k\)的斜率即可，由于凸包的边的斜率自左向右是递增的，所以我们可以维护一个队列，队头的斜率最小，并且自队头向队尾斜率是递增的。我们还需要注意求\(f[i]\)时候的\(k = st[i] + S\)，随着\(i\)的增加\(k\)也在增加，所以队列中小于\(k\)的斜率肯定也小于后面的\(k_i\)，不可能成为最优解的，所以在遍历队列找到第一个大于\(k\)的斜率时可以将小于\(k\)的斜率都删掉。

2、出队列尾

为了维护队列的单调性，插入新点\((sc[i],f[i])\)时，如果该点与之前相邻点的斜率不是高于之前队尾的斜率的，就要将队尾的斜率出队，踢出凸包的点集，直至找到一个合适的位置再插入队列。

四、代码逻辑

• 1、哨兵
  单调队列中存储的是点的编号\(i\)，其代表的斜率应该与其更接近队尾的相邻的点构成的斜率，所以初始情况下队头应该有个哨兵节点\(0\)。

    int hh = 0, tt = -1;
    q[++tt] = 0;//加入哨兵
  

• 2、出队头
  一条线至少有两个点构成，所以只有队列中有不少于两个点的情况下才能出队头，队头存储的是\((sc[q[hh]],f[q[hh]])\)，与后一个点\((sc[q[hh]+1],f[q[hh]+1])\)构成的斜率是\((f[q[hh]+1] - f[q[hh]]) / (sc[q[hh]+1] - sc[q[hh]])\)，当该斜率小于\(st[i] + S\)时就要出队头考虑下一个斜率，为了避免除法实现时需要变形下改为乘法。

    //出队头 注意这里是 hh < tt ，表示最少队列中有两个点的信息！
    while (hh < tt && f[q[hh + 1]] - f[q[hh]] <= (st[i] + s) * (sc[q[hh + 1]] - sc[q[hh]])) hh++;
  

  出队头一方面是为了自小到大找到第一个大于\(k\)的斜率，另一方面是为了删掉小于\(k\)的斜率，
  出完队头就找到了最优解\(j\)，开始更新\(f[i]\)，然后就是将\((sc[i],f[i])\)加入队列，同样是需要比较斜率大小，将该点放在合适的位置使得队列斜率递增，当\((f[i] - f[q[tt]]) / (sc[i] - sc[q[tt]]) > (f[q[tt]] - f[q[tt]-1]) / (sc[q[tt]] - sc[q[tt]-1])\)时才能加入到队尾。