凸性相关 ​

定义 ​

• 凸包：平面上包含所有点的最小多边形。
• 上凸壳、下凸壳：凸包的上下两部分。
• 离散函数的凸性：函数图像呈现为凸壳形状。

凸包性质 ​

• 上下凸壳的边斜率具有单调性。即对于上凸壳，从左到右各边斜率单调递减；对于下凸壳，从左到右各边斜率单调递增。
• 对于凸包内任意两点 $P(x_1,y_1)$ 和 $Q(x_2,y_2)$，线段 $PQ$ 上的所有点 $(x,y)=(tx_1+(1 - t)x_2,ty_1+(1 - t)y_2)$，$0\leq t\leq1$ 都不在凸包外。
• 对于任意一条经过凸包上某个点 $P(x_0,y_0)$ 且斜率固定为 $k$ 的直线 $y - y_0 = k(x - x_0)$，若要使 $k$ 最大（或最小），则该直线必然经过凸包上的点。进一步地，对于凸壳而言，其斜率 $k$ 必然在其邻边斜率范围之内。

函数凸性性质 ​

• 对于满足四边形不等式的序列划分问题，设将序列划分为 $m$ 段的最优值为 $f(m)$，则 $f(m)$ 关于 $m$ 必然具有凸性。
• 若函数 $y = f(x)$ 具有凸性，那么函数 $y = \max_{0\leq t\leq x} f(t)$ 或 $y = \min_{0\leq t\leq x} f(t)$ 仍然具有凸性。例如，若“恰好划分为 $m$ 段”的情况具有凸性，那么“至少划分为 $m$ 段”的情况一定具有凸性，但反之并不一定成立（虽然实际中未见过反例）。
• 在费用流问题中，设最小费用为 $C$，流量为 $F$，则 $C$ 关于 $F$ 具有凸性。若要指定某条边必选，可将其费用设为 $-\infty$，同样可证明其凸性。

联想点 ​

当题目中出现比值（如 $\frac{a}{b}$）、乘积（如 $a\times b$）等实数意义上的形式时，应联想到凸包。凸包通常可用于解决一些特殊的最优化问题。

建立凸包 ​

线性扫描法（离线做法） ​

设有点集 $S=\{P_1,P_2,\cdots,P_n\}$，首先将点按照横坐标 $x$ 从小到大排序。然后采用增量法构造凸包。假设已构造好前 $i - 1$ 个点的凸包 $CH_{i - 1}$，当加入点 $P_i$ 时，考虑凸包形态的变化。根据凸包的定义，若从凸包 $CH_{i - 1}$ 的末尾点开始，与 $P_i$ 形成的折线呈现凹的形状，则将末尾的这些凹进去的点删掉，剩余部分依然构成凸包。

插入法（在线凸包） ​

每次插入一个点 $P$，需找到其横坐标 $x_P$ 被凸包的哪条边跨过。若加入当前点 $P$ 后不会使凸包更优，则直接结束操作。否则，将 $P$ 点左右两边凹进去的点删掉。其正确性与上述线性扫描法类似。

旋转卡壳 ​

常见用途 ​

用于求解平面上的最远点对。

引理 ​

对于平面上的点集，其中任意一个点的最远点一定在该点集的凸包上。

流程 ​

基于凸包边的斜率单调性，我们按顺时针方向枚举凸包的边 $AB$。对于每一条边 $AB$，考虑在凸包上与之距离最远的点 $C$。由于凸包的性质，最远点 $C$ 也是按顺时针方向移动的。每次更新由边 $AB$ 的两个端点 $A$、$B$ 和最远点 $C$ 组成的点对作为答案。显然，通过这种方式可以考虑到所有不劣的解。

闵科夫斯基和 ​

定义 ​

设两个图形 $A$ 和 $B$，闵科夫斯基和 $A + B=\{a + b\mid a\in A, b\in B\}$，即由 $A$ 中任意一点与 $B$ 中任意一点相加得到的所有点组成的新图形。

基本结论 ​

若 $A$ 和 $B$ 是两个凸包，则它们的闵科夫斯基和 $A + B$ 仍然是一个凸包。

常见用途 ​

常用于凸包合并以及 $\{\max, +\}$ 卷积。下面主要讨论凸壳的合并。

流程 ​

每次将两个凸壳 $H_1$ 和 $H_2$ 的边拿出来，根据边的斜率进行贪心处理，类似于归并排序的方式。新凸壳的起始点是原凸壳 $H_1$ 和 $H_2$ 起始点之和。

感性理解 ​

为了使新的凸包能够包含所有由 $A$ 和 $B$ 中两点相加可能产生的点，需要让凸包尽可能大。

对 $\{\max, +\}$ 卷积的理解 ​

可以将两个多项式 $P(x)=\sum_{i = 0}^{n}a_ix^i$ 和 $Q(x)=\sum_{j = 0}^{m}b_jx^j$ 看成两个点集 $\{(i,a_i)\mid i = 0,1,\cdots,n\}$ 和 $\{(j,b_j)\mid j = 0,1,\cdots,m\}$。对于一个固定的横坐标 $k$，其 $\{\max, +\}$ 卷积的结果为 $\max_{i + j = k}(a_i + b_j)$，这恰好符合闵科夫斯基和的定义，即所有满足横坐标和等于 $k$ 的点的纵坐标和的最大值。

wqs 二分 ​

常见用途 ​

给定 $x$，求解凸函数 $f(x)$ 的值。

流程 ​

通过二分斜率 $k$，考虑斜率为 $k$ 的直线 $y = kx + b$ 与凸函数 $f(x)$ 的切点横坐标 $x_0$。由于凸性，横坐标 $x_0$ 关于 $k$ 具有单调性。核心在于找到使 $g(x)=f(x)-kx$ 取得最大值的点的横坐标 $x$，该点即为切点。

细节 ​

1. 二分的值域：需要分析凸壳上的边的斜率值域范围。通常只需考虑凸壳上第一条边和最后一条边的斜率，以此确定二分的上下界。
2. 二分的类型（整数或实数）：
   • 若为离散凸函数，通常凸壳上每条边的斜率为整数。
   • 然而，由于可能存在共线的点，直接二分实数可能出现问题。因此，建议二分整数。
   • 为处理共线情况，可钦定 $x$ 取最大或最小值，从而通过二分进行判定。
3. 构造解：朴素的 $wqs$ 二分可较容易地得到 $f(x)$，但在求解具体的 $x$ 时会受到共线情况的影响。（待补充完善，目前对此理解尚不透彻，网上也缺乏完全准确的资料）

wqs 二分和闵科夫斯基和的联系 ​

对于一个确定斜率 $k$ 的直线，设两个凸壳 $H_1$ 和 $H_2$，直线与 $H_1$、$H_2$ 的切点对应的截距之和，恰好等于 $H_1$ 和 $H_2$ 做闵科夫斯基和之后的凸壳与该直线切点的截距。这表明 $wqs$ 二分和闵科夫斯基和存在紧密联系。

这种联系主要源于具有凸性的问题通常可划分为若干子问题，最终通过合并子问题的解得到结果。闵科夫斯基和用于维护所有可能情况的解（以凸壳形式呈现），而 $wqs$ 二分则专注于维护一个特定的解（以切点形式呈现）。有时，我们可以先预处理出闵科夫斯基和的结果，再结合 $wqs$ 二分解决多次询问的问题。

斜率优化 ​

核心 ​

通过分析凸包的形态，确定最优解的选取方式。具体如下： 假设 $dp$ 方程形如 $dp[i]=\max_{j < i}(dp[j]+A + B\cdot i\cdot j)$。注意到经过点 $(x,y)$ 且斜率为 $k$ 的直线方程为 $y - y_0 = k(x - x_0)$，其截距为 $y - kx$。因此，我们将每个点看作 $(j,dp[j]+A)$ 的形式，要寻找斜率为 $-B$ 的直线经过某个点时的最大截距，所以必然保留的是上凸包。

常见算法 ​

1. 建立凸包：
   • 在线且横坐标无单调性：可使用李超线段树。
   • 其他情况：直接通过线性方式建立凸包。
2. 寻找最优点：
   • 在线且查询斜率无单调性：可通过二分凸包或在李超线段树上直接查询。
   • 其他情况：使用指针直接扫描。

例题 ​

1. [ABC356G] Freestyle：判定可行性相对简单，关键在于处理最优性问题。贪心和动态规划方法在此处难以突破，网络流方法也不太适用。假设仅使用两种 $style$，列出相关式子。其中不超过 $C$ 的条件在实数意义下大概率可使等式成立，此时可发现该式子与向量的等和线相关。为使整体取值尽量小，需先求出凸包，然后在凸包上进行二分查找。
2. [JOISC2022] 京都观光：直接求解较为困难。写出拐点相关的式子后，可发现其与凸包相关。