计算几何

Published: by Creative Commons Licence

  • Tags:

切比雪夫距离

二维情况

对于二维平面上两个点$(a,b),(c,d)$，它们的切比雪夫距离定义为

\[\max(|a-c|,|b-d|)\]

由于切比雪夫距离不容易被预处理，有时候需要先转换为曼哈顿距离进行处理。下面给出转换的数学公式：

\[|a-c|+|b-d|=\max(|(a+b)-(c+d)|,|(a-b)-(c-d)|)\]

证明方式比较简单，首先将右边公式转换为：

\[\max(|(a-c)+(b-d)|,|(a-c)-(b-d)|)\]

考虑两种情况，第一种$a-c$与$b-d$同号。那么右边的公式取值为$|(a-c)+(b-d)|=|a-c|+|b-d|$。而第二种情况下，$a-c$与$b-d$异号。那么右边的公式取值为$|(a-c)-(b-d)|=|a-c|+|-(b-d)|=|a-c|+|b-d|$。因此证明了等式的成立。

利用这个公式我们可以先将所有平面上的点$(x,y)$转换为$(x+y,x-y)$的形式，之后计算各个点间的切比雪夫距离就可以得到原平面的曼哈顿距离。同理，如果我们将平面上的点$(x,y)$转换为$(\frac{x+y}{2}, \frac{x-y}{2})$，之后计算各个点之间的曼哈顿距离，那么就可以得到原平面的切比雪夫距离。

题目1：给定$n$个二维点$(x_1,y_1),\ldots,(x_n,y_n)$，现在要求找到一个中心$(x,y)$，要求最小化所有二维点到中心的最大曼哈顿距离。即记$f(x,y)=\max_i |x_i-x|+|y_i-y|$，要求找到$\min_{x,y} f(x,y)$。其中$n\leq 10^5$，且$0\leq x_i,y_i \leq 10^{18}$

这样的问题明显是二分，我们先二分出最小的距离。之后发现每个顶点可到达的区域是一个菱形。我们可以将曼哈顿距离转成且比学夫距离后，发现每个定点可达区域是一个正四边形。我们只需要判断这些正四边形是否有交集即可。

三维情况

问题1：给定$n$个三维整数点$(x_1,y_1,z_1),\ldots,(x_n,y_n,z_n)$，现在要找到一个整数中心$(x,y,z)$，要求最小化所有点到中心的最大曼哈顿距离。即记$f(x,y,z)=\max_i |x_i-x|+|y_i-y|+|z_i-z|$，要求找到$\min_{x,y,z} f(x,y,z)$。其中$n\leq 10^5$，且$0\leq x_i,y_i\leq 10^{18}$

这个问题是不能通过价位那个曼哈顿转切比雪夫来解决的，因为固定最小距离$D$，会发现每个点的可达区域实际上是一个八面体。我们无论如何旋转都无法让它变成一个规则的六面体。

我们可以发现八面体带来的约束的格式一定为：

\[\begin{aligned} \ldots \leq& x+y+z &\leq \ldots\\ \ldots \leq& -x+y+z &\leq \ldots\\ \ldots \leq&x-y+z &\leq \ldots\\ \ldots \leq& x+y-z &\leq \ldots \end{aligned}\]

我们引入一些新的变量：

\[\left\{ \begin{array}{lcr} a&=&-x+y+z\\ b&=&x-y+z\\ c&=&x+y-z \end{array} \right.\]

可以发现有$x+y+z=a+b+c$，因此我们可以将所有约束重写为：

\[\begin{aligned} \ldots \leq& a+b+c &\leq \ldots\\ \ldots \leq& a &\leq \ldots\\ \ldots \leq& b &\leq \ldots\\ \ldots \leq& c &\leq \ldots \end{aligned}\]

要从中计算一个可行解是非常简单的。

下面我们考虑整数带来的影响，由于$(x,y,z)$都是整数，而$x=\frac{b+c}{2}$，$y=\frac{a+c}{2}$，$z=\frac{a+b}{2}$。因此$a=b=c\pmod 2$。

我们可以暴力枚举$a,b,c$的奇偶性（$2a'+k$,$2b'+k$和$2z'+k$，其中$k\in {0,1}$）。于是乎我们可以$O(n)$求出一组解或报告无解。加上二分，总的时间复杂度为$O(n\log_2M)$。其中$M$是精度。

曼哈顿距离的组合

最近从一个atcoder的问题中学了一个新的东西，记录一下。

给定序列$2^0,2^1,2^2,\ldots, 2^k$，我们从$(0,0)$出发，我们可以不断从序列中选取一个整数x并删除，之后向四个方向中的一个方向移动距离x。重复这个过程直到序列为空。

我们可以证明通过上面这个流程可以从$(0,0)$移动到距离$(0,0)$曼哈顿距离为奇数且小于$2^{k+1}$的所有整数坐标顶点。

至于怎么构造到$(x,y)$的路径，我们可以选择最后一个数字$2^k$，之后沿着四个方向移动，判断哪种方案移动后到$(0,0)$的距离小于$2^k$，选择它即可。递归这个流程就可以构造出解决方案了。

斜线转坐标轴平行线

问题1：平面上有$n$个坐标不同的点$(x,y)$。对于顶点$(x_0,y_0)$，我们可以用过该点的两条斜率分别为$\frac{\pi}{4}$与$-\frac{\pi}{4}$的直线将整个二维平面划分为四个区域。我们可以按照四个区域相对于$(x_0,y_0)$的位置将其分为上下左右四个方向。现在我们希望对每个点统计处于其上方区域、下方区域、左边区域、右边区域（不存在与区域的划分线上）的顶点数目。

斜线不是很好处理，我们可以发现若一个顶点$(a,b)$落在$(x_0,y_0)$的右区域上，这时候有$(a-x_0,b-y_0)$的极角落在$(-\frac{\pi}{4},\frac{\pi}{4})$。这意味着

\[-(a-x_0)\leq b-y_0\leq a-x_0\\ \Rightarrow \left\{ \begin{array}{ccc} y_0+x_0&\leq &b+a\\ y_0-x_0&\geq &b-a \end{array} \right.\]

这里我们可以将所有点的坐标$(x,y)$变化成$(y-x,y+x)$，这样一个点$A$处于$B$的右区域，当且仅当这个$A$变换后的顶点处于$B$变换后的顶点的左上方。

对于其余三个方向我们可以做同样的变化。事实上由于这是线性变换，因此可以很容易得出：右区域对应左上，左区域对应右下，上区域对应右上，而下区域对应左下。

现在问题就变成了统计每个顶点左上，左下，右上，右下各有多少顶点，离散化后用BIT统计即可。

一道题目。

问题2：考虑将问题1中的$\frac{\pi}{4}$和$-\frac{\pi}{4}$替换为任意有理数$\frac{p}{q}$和$\frac{q}{p}$。回答问题1。

考虑$(x_0,y_0)$右侧的公式：

\[y_0-(x-x_0)\frac{p}{q}\leq y\leq y_0+(x-x_0)\frac{p}{q}\]

我们将不等式几部分都乘上$q$得到：

\[y_0q-(xp-x_0p)\leq yq\leq y_0q+(xp-x_0p)\]

这个等式实际上和$\frac{\pi}{4}$和$-\frac{\pi}{4}$的非常类似。因此我们可以先将所有点的横坐标乘上$p$，纵坐标乘上$q$之后问题就变成了$\frac{\pi}{4}$和$-\frac{\pi}{4}$的划分问题。

求三角形内心坐标

问题：在圆心为原点，半径为1的圆周上，存在$n$个点（$n\leq 3000$）。现在我们随机从中取出三个不同的点，考虑三个点构成的三角形的内心坐标。问三角形内心坐标的期望。

原题是https://atcoder.jp/contests/agc039/tasks/agc039_d。做法是套公式。考虑复平面，根据欧拉公式有:对于所有实数$x$，有：

\[\exp(ix)=\cos(x)+i\sin(x)\]

同时，假设选择的三个点为$\exp(i\varphi_1),\exp(i\varphi_2),\exp(i\varphi_3)$，且满足$0\leq \varphi_1 < \varphi_2 < \varphi_3<2\pi$，那么由这三个点组成的三角形的内心一定为

\[\exp(i\frac{\varphi_1+\varphi_2}{2})-\exp(i\frac{\varphi_1+\varphi_3}{2})+\exp(i\frac{\varphi_2+\varphi_3}{2})\]

这样我们只要暴力两两枚举即可解决这个问题，时间复杂度是$O(n^2)$以及一个很大的常数，因为$sin$和$cos$函数会被调用$O(n^2)$次。

多维偏序问题

问题1：给出$n$二维平面上的顶点$(x_i,y_i)$，满足$x_i,y_i\geq 0$，同时给出$m$个请求，每个请求查询左下角为$(0,0)$，右上角为$(r,t)$的矩形中有多少平面上顶点存在

这是个典型的二维偏序问题，我们可以提前所有顶点按照$x$坐标进行排序，如果$x$坐标相同，则按照$y$坐标排序。对请求通样这样处理，并且利用双指针技术在请求范围内的所有顶点加入后回答请求，这时候请求就变成了有多少顶点的$y$坐标小于等于$t$，这可以用BIT或线段树维护。总的时间复杂度为$O((n+m)\log_2n)$。

问题2：给出$n$三维的顶点$(x_i,y_i,z_i)$，满足$x_i,y_i,z_i\geq 0$，同时给出$m$个请求，每个请求查询左下角为$(0,0,0)$，右上角为$(r,t,d)$的矩形中有多少顶点存在

这个是三维偏序问题，与所有偏序问题一样，我们可以通过提前排序消除一个维护带来的影响。剩下的就是二维数据的维护了，你可以选择树套树，也可以选择CDQ分治。树套树时间复杂度为$O((n+m)(\log_2n)^2)$，空间复杂度为$O(n(\log_2n)^2)$，CDQ分治的时间复杂度为$O((n+m)(\log_2(n+m))^2)$，空间复杂度为$O(n+m)$。

问题3：给出$n$三维的顶点$(x_i,y_i,z_i)$，满足$x_i,y_i,z_i\geq 0$，同时给出$m$个请求，每个请求查询左下角为$(l,b,f)$，右上角为$(r,t,d)$的矩形中有多少顶点存在

这个问题类似于问题2，区别在于要去我们计算的是落在一个三维矩形中有多少顶点。一种简单的方式就是利用容斥，记$S$表示落在由$(0,0,0)$与$(r,t,d)$矩形中的所有顶点，记$X$表示满足$x<l$的顶点集合，同理定义$Y$和$Z$，那么我们要计算的落在左下角为$(l,b,f)$，右上角为$(r,t,d)$的矩形中顶点数目，等价于计算：$\mid \overline{X}\cap \overline{Y}\cap\overline{Z}\mid$。这是个简单的容斥，可以转换为$2^3$个左下角为$(0,0,0)$的矩形顶点数的统计。

一道CF的例题。

一些游走问题

问题1：给出一组二维向量$v_1,v_2,\ldots,v_n$，你要选择一组符号$s_1,s_2,\ldots,s_n$，其中$s_i\in {-1,1}$。其中$\mid v_i \mid \leq D$，要求选择的符号满足$\mid \sum_{i=1}^ns_iv_i \mid\leq \sqrt{2}D$。

如果只有两个向量的话，我们可以构造一个半径为$D$的圆，我们将两个向量以及其负向量加入，可以证明至少会有两个向量是处于同一个$90$度半圆内，而这个半圆内的任意两点距离都不会超过$\sqrt{2}D$，这与我们的符号也就选好了。

现在考虑一般情况，此时至少有三个向量，我们取这样三个向量以及其负向量加入到半径为$D$的圆内，此时，至少有两个向量处于同一个$60$度半圆内，而这个半圆内任意两点的距离都不会超过$D$，因此我们找出这两个向量，并合并为一个向量即可。重复这个过程直到向量数目少于3为止。如果剩余向量数为2，那么需要特殊处理，否则任意选一个符号就好了。

直线（线段）排序的优化技巧

考虑现在有$n=10000$条二维直线（所有直线都不与$Y$轴平行，且任意两条直线最多有一个交点）。之后给定$m=10000$个请求，第$i$个请求给定一个数$x_i$，要求将所有直线根据与直线$y=x_i$交点的纵坐标从小到大排序，并输出排序后的编号。

要计算交点坐标，有$O(1)$的做法，因此如果我们使用快速排序或选择排序，那么时间复杂度将为在$O(nm\log_2n)$。

下面我将提出一种排序技术，可以将时间复杂度优化到$O(n(m+n))$。

首先我们离线请求，将请求按照$x_i$从小到大进行排序。之后我们逐个处理请求，但是处理每个请求的时候，我们使用的排序算法是插入排序。为什么要使用最坏时间复杂度为$O(n^2)$的插入排序呢？因为插入排序在序列本身有序的情况下是线性的。下面我们给出严格的时间复杂度分析。

我们考虑插入排序的时间复杂度，其本质是扫描整个序列一次，并且每一次解决一个逆序对时对时间复杂度贡献$1$，因此当序列完全为逆序的时候，总共有${n\choose 2}$个逆序对，这时候时间复杂度为$O(n^2)$。

但是考虑到直线排序的特殊性，对于任意两条直线$A$与$B$，直线$A$与$B$的偏序关系最多改变一次（由$A\lt B$变成$A\gt B$)。即除了第一次的插入排序后，之后每个逆序对对时间复杂度的贡献仅为$O(1)$，而插入排序的其余部分是线性的。

因此总的时间复杂度为$O(n(m+n))$。

最近点对

问题1：给定$n$个二维点，要求计算最近一对点的距离。（这里用的距离是欧几里得距离）

算法导论上给出了一个最近点对的算法。

问题2：给定$n$个二维点，要求计算最近一对点的距离。（这里用的距离是曼哈顿距离）

我们可以先将所有点按照$x$坐标排序，如果$x$相同就按$y$排序。之后每个顶点只和前面的点计算最短距离，而全局的最近点一定能从这些最短距离中取到。

之后我们对于一个顶点$p=(x_i,y_i)$，我们可以将左边的所有顶点分成两部分，一部分的$y$坐标恒大于等于$y_i$，另外一部分则小于$y_i$。

注意对于左上顶点$lt=(x_j,y_j)$，其与$p$距离为$x_i-y_i-x_j+y_j$，考虑到$x_i-y_i$是常数，因此我们对上平面的点维护最小的$-x_j+y_j$即可。同理对于下平面的顶点$lb=(x_k,y_k)$，其与$p$距离为$x_i+y_i-x_j-y_j$，我们只需要对下平面的点维护最小的$-x_j-y_j$即可。

上面提到的内容可以通过维护两颗线段树实现。因此总的时间复杂度为$O(n\log_2n)$。

多条线段判断是否有交点

给定$n$条线段，判断是否存在至少一对线段有交点。

我们可以从左到右扫描所有线段。将线段左端点视作加入事件，右端点视作离开事件。

加入事件，记当前$x$为$x_0$，我们二分找到插入的位置（按照线段于$x=x_0$这条线的交点的纵坐标排序），之后判断前驱和后继与新线段是否有交点，有则直接输出解，否则加入线段。

删除事件，删除线段后，还需要重新判断一下前驱和后继是否有交点，有则直接输出解，否则继续流程。

上面的做法是不支持垂直线段的。要支持垂直线段可以这样做，以线段中心为轴稍微旋转线段。或者可以直接特殊处理垂直线段和垂直线段的交点，以及判断垂直线段与其余线段的交点。

总的时间复杂度为$O(n\log_2n)$。

曼哈顿距离最小生成树

给定二维平面上$n$个点，每对点之间存在一条边，边权等于二者的曼哈顿距离。要求找到一株最小生成树。这里$n\leq 10^5$。

一种简单的思路就是用不用最小堆优化的Prim算法，时间复杂度为$O(n^2)$，但是还是差点意思。

最近在Topcoder上学到了可以$O(n\log_2n)$计算曼哈顿距离最小生成树的技术。下面讲解一下。

考虑任意一个点$P$，我们以其为中心，将平面分成8部分。

http://community.topcoder.com/i/education/lineSweep/octants.png

假设$Q$为西北平面中离$P$最近的顶点，而$R$是另外任意一个顶点。可以发现假如$PR$是最小生成树中的一条边，那么$QR$与$QP$不可能同时出现，但是二者的边权均不会超过$PR$，因此我们可以用$QR$或$QP$中的一条边替代$PR$。换句话说，就是$PR$这条边我们在计算最小生成树的时候不需要考虑。

这样一来，每个顶点最多有$8$条边需要考虑，因此总共需要考虑的边的数目仅为$8n$。这时候我们利用Kruskal算法就可以直接$O(n\log_2n)$出解了。

接下来我们讨论如何为每个顶点找到这$8$条边。我们先考虑如何为每个顶点找到西北方向的最近的顶点，而其它方向可以通过这个方法推广出去逐一解决。

我们发现对一个顶点$P$有贡献的其余顶点$Q$都满足$Q.x+Q.y\leq P.x+P.y$且$Q.y\geq P.y$。如果没有$Q.y\geq P.y$这个条件，那么我们可以将所有顶点按照两个维度的和进行排序处理，非常简单。但是现在加上了$Q.y\geq P.y$这个条件，我们就不能这么做了。但是我们可以用分治的技术解决这个问题。

我们定义$dac(S)$表示对$S$代表的点集计算最近的西北部点，同时输入的$S$按照$y$坐标从小到大排序（如果$y$相同，则按$x$进行排序），而处理完后，$S$按照两个维度的和从小到大排序。

对于一个请求，我们将输入分成上下两个平面中的顶点，并分别递归解决。之后我们发现下平面对上平面是没有贡献的，但是上平面可能对下平面存在贡献，且上平面的顶点$Q$，对于下平面的顶点$P$都是满足$Q.y\geq P.y$这个条件的。因此我们只需要直接处理即可。之后用合并排序的方式将上下两个平面的顶点集合合并。

很显然上面的流程时间复杂度是$O(n\log_2n)$的，我们要为$8$个平面都重复上面的流程，因此总的时间复杂度为$O(8n\log_2n)$。

提供一道Topcoder題目SRM 760 ComponentsForever。

一些圆相关问题

问题1：给定一个$w\times h$的矩形平面，给定$n$个落在这个矩形平面内的顶点$(x_1,y_1),\ldots,(x_n,y_n)$。现在要求找到半径最大的一个圆，要求圆心落在矩形内，且在圆中（圆周上的不算）最多有$k$个顶点。其中$1\leq w,h\leq 10^3$，$0\leq x_i\leq w,0\leq y_i\leq h$，$0\leq k<n\leq 10^3$。

提供一道题目。

我们重新理解一下$k$的含义，它的意思实际上是指我们最多可以从$n$个点中删除$k$个点，并且要求其余点都落在圆周或圆外。问最大的圆半径是多少。

不难发现，我们的圆周上至少有一个顶点。我们可以暴力枚举这个顶点，共$n$种可能性。

现在考虑顶点$1$在圆周上，我们可以发现圆的半径和解是否存在具有单调性，我们可以二分圆的半径。

现在的问题已经转换成了，判断是否存在一个半径为$r$的圆，最多$k$个顶点都落在其内，且顶点$1$落在圆周上。

这个问题怎么求解呢。我们可以通过圆心是否存在来求解。具体做法就是，可以发现圆心一定落在从以顶点$1$为圆心半径为$r$的园的圆周上，记这个圆为$A$。这时候我们可以这样理解，我们发现圆周的每部分都被若干个圆覆盖，比如考虑以顶点为$c$，半径为$r$的圆，记这个圆为$B$，可以发现$A$的圆周的连续一段被$B$所覆盖。我们可以用一些数据结构来维护这些覆盖信息，即我们可以最终将圆周分成若干段，每一段都被相等数量的其它圆所覆盖。只需要$A$存在一段圆周被不超过$k$个其它圆所覆盖，就一定有解（我们取该段圆周上任意一个点作为圆心即可）。

上面这个过程实际上可以$O(n\log_2n)$完成。整个流程的时间复杂度为$O(n^2\log_2n\log_2M)$。

上面我们可以应用一种随机化的技术，这样可以将时间复杂度中的$\log_2M$去除，这样最终时间复杂度为$O(n^2\log_2n)$。

问题2：在二维平面上给定$n$个红点和$m$个黑点。要求找到半径最大的圆的半径，满足这个圆中至少包含一个红点，且不含任何黑点。（一个圆周上的点可以认为是在圆内，也可以认为是在圆外）。如果这个圆可以任意大，就输出$-1$。其中$1\leq n,m\leq 1000$。

这是一道原题。

首先我们考虑什么情况下圆会任意大，这时候至少有一个红点落在所有点组成的凸包上。接下来我们认为圆不能任意大。

一般的思路是可以发现圆周上至少有3个点才能确定一个圆，因此我们可以直接枚举所有的三个点确定的圆，这样的话时间复杂度为$O(n^4)$。

考虑假如存在满足条件的半径为$R$的圆，则对于任意$r\leq R$，半径为$r$的满足条件的圆也一定存在（我们可以在$R$圆中划出一个更小的圆，覆盖其中的一个红点即可）。因此我们可以用二分来找到最大的圆的半径。

在给定半径为$r$的情况下，可能的圆非常多，我们不可能一个一个枚举。可以注意到如果存在一个半径为$r$的覆盖圆，也一定存在一个半径为$r$覆盖圆，有至少一个顶点落在圆周上（稍微挪动一下圆心即可）。有了这个性质，我们就可以枚举每个点，计算这个点落在圆周上，圆心相对于这个点的弧度可能是哪些（这是一个经典问题了）。

枚举每个点的时间复杂度为$O((n+m)\log_2(n+m))$，因此一轮二分的check所花费的时间复杂度为$O((n+m)^2\log_2(n+m))$。配合二分的时间复杂度为$O((n+m)^2\log_2(n+m)\log_2 M)$，其中$M$与精度有关。

但是这里有一个小小的优化思路，之前我们是外面二分圆大小，内部枚举所有边缘点来实现的，现在我们外部枚举所有边缘点，内部二分圆大小。注意到以红点落在圆边缘的情况下，随着半径的增大，覆盖圆的存在性单调减少，因此可以二分直接查出红点落在圆边缘下最大的覆盖圆，记半径为$low$。之后我们二分计算蓝点$b$落在圆边缘下最大的覆盖圆，记为$high$，如果$high\geq low$，则对于任意半径为$r\in [low,high]$，都存在一个半径为$r$的覆盖圆，覆盖一个红点且$b$落在圆边缘上（如果不存在，记$k$为最小的$b$落在圆周的覆盖圆的半径，此时$k>low$且正好一个红点落在圆周上，这与$low$的定义相悖）。

当然上面还没有达到优化的作用，因为时间复杂度还是没有变。但是接下来我们应用一个技巧，就是设$L$为目前为止找到的最大覆盖圆的半径，则接下来处理某个点$x$并进行二分之前，我们先检测一下是否存在一个半径为$L$的覆盖圆，$x$落在圆周上。如果不同过，则不必进行后面的二分。

我们可以发现检测次数一共是$n+m$次，这部分的时间复杂度为$O((n+m)^2\log_2n)$，二分次数则很特殊。我们可以为每个顶点赋予一个权值，这个权值恰好等于以它落在圆周上最大半径的覆盖圆的半径。可以发现二分次数实际上是我们枚举的顶点的一个特殊的递增序列（如果一个顶点的权值比之前所有枚举的顶点权值都要大，则二分次数增加1）。如果我们提前打乱所有顶点的处理顺序（保持红点在所有蓝点处理前被处理），则可以证明二分的总次数的期望为$O(\log_2n)$。因此二分的时间复杂度为$O((n+m)\log_2n\log_2M)$。总的时间复杂度为$O((n+m)^2\log_2n)$。

题目3：给定一个圆和$n$个不同的点，考虑这些点两两之间的连线，要求计算其中有多少条线与圆相交。保证这些直线都不可能与圆相切。其中$1\leq n\leq 10^6$。

首先我们将点分成圆内和圆外的，问题实际上要我们找有多少直线不与圆相交，而这些直线的两个端点肯定都在圆外。

对于圆外顶点$A$和$B$，记两个顶点与园的切点分别为$a,b$和$c,d$，过它们的直线是否与圆相交，当且仅当四个切点错位排序，比如说$a,c,b,d$。

而由于错位排序经过循环依旧是错位排序，因此问题变成了给定一个序列$a_1,a_2,\ldots,a_{2n}$，其中$1,2,\ldots,n$各出现$2$次，问存在多少对错位排序对。这个可以先对右边界排序后通过BIT来解决。时间复杂度为$O(n\log_2n)$。

一类求凸包交集问题

题目1：给定多个凸包，计算它们的交集的面积。其中凸包的顶点数之和$n$不超过$10^5$。

这是经典的半平面交算法，时间复杂度为$O(n\log_2n)$。

题目2：二维平面上有$n$个不同的整数顶点$v_1,v_2,\ldots,v_n$。现在希望确定一个整数中心顶点$c$，要求最小化$\max_{i=1}^ndist(v_i,c)$，其中$dist(a,b)=|a.x-b.x|+|a.y-b.y|$，即两者之间的曼哈顿距离。其中$n\leq 10^6$。

提供一道类似的题目。

很显然我们可以通过二分将问题转换为检测多个棱形是否有公共整数点。由于中心和大小都是整数，因为问题也等价于判断多个棱形是否有交集。

这可以直接通过半平面交算法来完成。由于我们不需要对边进行排序（边的弧度仅四种），因此我们可以$O(n)$完成半平面交算法。时间复杂度为$O(n\log_2M)$。

还有一种非常简单的做法就是将曼哈顿距离转成切比雪夫距离，这里棱形就变成了规则的矩形，矩形判交非常容易。时间复杂度为$O(n)$。

一类二维点消除问题

题目1：给定$n$只妖怪和$m$个英雄。每个英雄可以按任意顺序行动正好一次。当一个英雄行动时，它向某个方向射出一发弓箭，弓箭会杀死第一只遇到的怪物，之后怪物和弓箭都消失。现在要求对每个怪物计算它是否有可能被英雄杀死。其中$1\leq n\leq 10^3,1\leq m\leq 7$。

一道原题。

我们可以单独考虑是否有机会能杀死某只怪物。考虑某只怪物，如果一个英雄最终将杀死它，那么这个英雄与怪物之间存在的其它障碍物需要由其他英雄消灭。

我们需要考虑所有英雄的行动顺序（共$m!$）种，之后由第一个英雄负责击杀目标怪，而中间的怪物则由其余英雄按照他们的行动顺序决定。

这里我们递归注意剪枝的话，每次给定排列，判断能否成功的时间复杂度实际上是$O(m^2)$，总的时间复杂度为$O(nm^2m!)$，能过。

线段包围面积问题

题目1：给定$n$条水平栅栏和$m$条垂直栅栏，之后在点$(0,0)$放一头牛，问这头牛可以移动的区间的面积是多少（牛不能跨过栅栏，且不会有栅栏覆盖点$(0,0)$）。其中$1\leq n,m \leq 1000$。

离散化所有的线段后，可以构建一个网格图，在网格图上搜索可达区间即可。时间复杂度为$O(nm)$。

凸包问题

题目1：给定$A$, $B$，$a_1,\ldots,a_n$，$b_1,\ldots,b_n$，$c_1,\ldots,c_n$，要求找到一组非负未知数$x_1,x_2,\ldots,x_n$，满足

  • $\sum_{i=1}^na_ix_i\geq A$
  • $\sum_{i=1}^nb_ix_i\geq B$

且要求最小化$\sum_{i=1}^nc_ix_i$，输出任意一组可行解。其中$n\leq 10^5$，结果允许是浮点数。其中$0<a_i,b_i,c_i$

这是个简单的线性规划问题，通过单纯形算法可以解决。

我们也可以通过一些有严格时间复杂度保证的算法来解决这个问题。

先令$a_i:=a_i/c_i$，$b_i:=b_i/c_i$。这时候约束的形式不变，但是最小化的公式变成$\sum_{i=1}^nx_i$。

我们可以认为是需要按一定比例将所有向量$(a_i,b_i)$合成，之后让向量可以尽快抵达顶点$(A,B)$。我们可以将$a_i,b_i$看成二维平面上的点，之后加入$(0,0)$后形成凸包，而上凸包与直线$(0,0)$和$(A,B)$的交点就是我们的最优的比例合成的向量。还有一种情况就是不存在交点，这时候我们可以保证最终的向量等于某个已有向量，直接暴力枚举即可。时间复杂度为$O(n\log_2n)$。

题目2：给定$A$, $B$，$a_1,\ldots,a_n$，$b_1,\ldots,b_n$，$c_1,\ldots,c_n$，要求找到一组非负未知数$x_1,x_2,\ldots,x_n$，满足

  • $\sum_{i=1}^na_ix_i\leq A$
  • $\sum_{i=1}^nb_ix_i\leq B$

且要求最大化$\sum_{i=1}^nc_ix_i$，输出任意一组可行解。其中$n\leq 10^5$，结果允许是浮点数。其中$0<a_i,b_i,c_i$

提供一道题目。

先令$a_i:=a_i/c_i$，$b_i:=b_i/c_i$。这时候约束的形式不变，但是最大化的公式变成$\sum_{i=1}^nx_i$。

现在来理解问题，现在给出一组向量$(a_1,b_1),\ldots,(a_n,b_n)$，要求找到一组非负因子$\alpha_1+\alpha_2+\ldots+\alpha_n=1$，使得沿着向量$\sum_{i=1}^n\alpha_i\times (a_i,b_i)$最慢离开以$(0,0)$为左下角，$(A,B)$为右上角的四边形。可以发现混合得到的向量一定处于这些点组成的凸包中。

而这样的混合得到的最优向量，只可能是凸包上的顶点，或者凸包与向量$(A,B)$的交点。

总的时间复杂度为$O(n\log_2n)$。

题目3：现在在第一坐标系中有$n$个不同的点$(x_1,y_1),\ldots,(x_n,y_n)$。称点$i$是可能最优的，当且仅当在第一坐标系中存在一个向量$(a,b)$，满足$\forall j\neq i$，有$ax_i+by_i<ax_j+by_j$成立。找出$n$个点中所有可能最优的点。

提供一道题目。

我们根据这些点建立一个凸包，考虑点积的意义，$a\odot b=|a||b|\cos \theta$。即点$i$是最优的，当且仅当存在一个方向，点$i$投影到这个方向上的长度严格最短。很显然可能的候选人只可能是在凸包的顶点上（凸包的边上的点是不满足的）。

记$L$为凸包上最左边的点（如果多个取最下边的），$B$为凸包上最下边的点（如果多个取最左边的点）。而$L$到$B$之间的所有凸包上的顶点都是可能最优的。

时间复杂度为$O(n\log_2n)$。

题目4：现在在第一坐标系中有$n$个不同的点$(x_1,y_1),\ldots,(x_n,y_n)$。称点$i$是可能最优的，当且仅当在第一坐标系中存在一个向量$(a,b)$，满足$\forall j\neq i$，有$ax_i+by_i>ax_j+by_j$成立。找出$n$个点中所有可能最优的点。

我们根据这些点建立一个凸包，考虑点积的意义，$a\odot b=|a||b|\cos \theta$。即点$i$是最优的，当且仅当存在一个方向，点$i$投影到这个方向上的长度严格最长。很显然可能的候选人只可能是在凸包的顶点上（凸包的边上的点是不满足的）。

记$T$为凸包上最上边的点（如果多个取最右边的），$R$为凸包上最右边的点（如果多个取最上边的点）。而$R$到$T$之间的所有凸包上的顶点都是可能最优的。

时间复杂度为$O(n\log_2n)$。

集群问题

题目1：给定$n$个不同的二维平面点，现在要将这些顶点进行分类。对于任意类型$A,B$，记$x$为$A$中最远两点的距离，记录$y$为$A$到$B$中的顶点对之间的最近距离。这里的距离是指欧几里德距离。要求$x<y$一定成立。现在问对于$k=1,\ldots,n$，是否存在一种分类方案，将$n$个点正好分入$k$类，且每类非空。这里$1\leq n\leq 5000$。

提供一道题目。

对于一个点的子集$S$，$S$是否能作为一个分类，与其它类型包含哪些元素是没有任何关系的。因此我们相当于要找到哪些子集可以作为一个分类。

考虑如果我们把顶点$a,b$放入同一个分类，记两点的距离为$D(a,b)$。可以发现与$a$或$b$相邻的距离它们小于$D(a,b)$的顶点也会被加入这个分类中。这会导致一些展开问题，我们可以按照边权从小到大枚举这些边，这样就可以避免展开。

现在考虑一个连通分量，我们为其维护一个dp，$dp(i)$表示这个连通分量是否能分成$i$个分类。

考虑任意一个连通块，和一条即将加入的新边$(a,b)$，假设现在$a$和$b$处于不同的连通块。考虑dp会怎么变化。一种分类方案是不出现任何分类同时含有$a,b$中的元素，这个可以通过对$a,b$进行卷积得到。而还有一种分类方案是存在至少一个分类跨越$a,b$中的元素，任意考虑一个跨越的分类$A$，可以发现根据根据上面提到的展开，$A$至少会包含$a,b$中的所有元素。当然即使如此，也不能保证$A$是一个正确的分类，因为此时$A$内部的最远点对的距离可能变大了。

我们可以在维护连通块的同时顺便维护一下连通块中加入了多少边，对于大小为$x$的连通块，如果加入$x^2$条边，那么这时候$A$就变得合法了。

上面的总的时间复杂度看起来像$O(n^3)$（共$n$次合并，每次合并需要$O(n^2)$计算卷积），但是实际上这类似于一类树上DP问题，任意两个点只会在它们的LCA处产生1的贡献，因此如果小心实现的话，时间复杂度实际上是$O(n^2)$。

Delaunay triangulation问题

相关的文章。

给定一组点，找到以这些点为中心的Voronoi图（下图的黑点为中心）。Voronoi图将空间分为若干凸包，其中平面中距离点$i$最近的所有的点都落在以$i$为中心的凸包中。

而要找Voronoi图，我们需要解决它的对偶问题，Delaunay triangulation。其表示由这些中心为三角形顶点，将所有顶点形成的凸包划分为若干个三角形，满足所有三角形的外切圆内（圆周上不算），都不会包含其余顶点。

有不少算法可以实现Delaunay triangulation，且时间复杂度可以达到$O(n\log_2n)$，当然我一个都不会。

Delaunay triangulation的一些用处：

  • 三角形的边最多有$3n-6$条。
  • 欧几里德最小生成树是三角化后所有三角形的边的子集。
  • 所有三角形的外切圆内（圆周上不算），都不会包含其余顶点。
  • 对于任意顶点，距离它的最近点一定在三角化后与它拥有公共边。

一道题目。

多边形相交

两个多边形相交

两个多边形相交当且仅当下面一个条件满足：

  • 一个多边形被包含在另外一个多边形内部
  • 两个多边形存在两条边有交点

两个等速旋转的多边形是否相交

提供两个边数为$n$和$m$的多边形$A,B$，分别按照点$P,Q$旋转。且旋转的角速度相同。问两个多边形是否有可能相交。

提供一道题目。

考虑将多边形$A$作为参照系，则可以发现$P$点不动，$Q$点会绕着$P$点距离为$dist(P,Q)$的圆周上旋转。而多边形$B$相对于$Q$点是不动的。

如果$A$与$B$有相交，那么必定存在下面一种情况：

  1. $A$的某个顶点和$B$的某条边有交点
  2. $B$的某个顶点和$A$的某条边有交点

我们不妨认为是第二种情况。这时候考虑到$B$的某个顶点$b$和$A$的边$(a_1,a_2)$有交点，那么边$(a_1-b,a_2-b)$一定和圆周有交点。

上面的做法的时间复杂度为$O(nm)$。

凸包技巧

假设一开始我们有一个空的集合$Y$。下面我们要支持下面几种操作：

  • 向集合插入一个一阶多项式。
  • 询问集合中所有一阶多项式在某个特定$x=x_0$值处的值的最大值。

两个操作发生次数都不会超过$10^6$次，并且询问之前一定保证集合非空。

很显然暴力是不好的，暴力是解决不了问题的，暴力的时间复杂度是$O(nm)$，$n$为插入执行次数，$m$为询问执行次数。

小学数学就教过我们，一阶多项式为$y=ax+b$，它一定是一条直线。如果$a$为正数，那么直线一定是递增的，如果$a$为负数，则直线对应是递减的，如果$a$为0，则直线是水平的。

我们记一个新的函数$f$，定义为：

\[f(x)=\max_{y\in Y}y(x)\]

由于一阶多项式是连续的，因此$f$也是一个连续函数。它的实际表现是一幅折线图。

对于集合中的某个一阶多项式$y$，如果对于任意$x\in [l,r]$，都有$y(x)=f(x)$，则称$[l,r]$为函数$y$的优势区间。如果$Y$中函数没有优势区间，那么我们可以将其从$Y$中剔除而不影响查询的结果。稍加推导就可以证明一个函数的优势区间一定是连续的，所有函数的优势区间是互不相交的（两个区间端点分配给任意一个一阶多项式），且所有函数的优势区间的并一定是全域。

我们称一阶多项式$y$的优势区间中的下确界为$y$的起始作用点。很显然起始作用点和直线的斜率是息息相关的，斜率越大，起始作用点越大。我们可以利用这个性质，维护一个有序集合，集合按照直线的斜率排序（对应的也是按照起始作用点排序）。

下面说明如何完成两种操作。

对于插入操作，我们对集合进行二分查找，找到插入点。如果集合中存在与插入直线拥有相同斜率的直线，那我们就选择处于上方的那一条。之后处理插入点的前驱，计算前驱与插入直线的交点，如果交点在前驱的起始作用点之前，那么前驱就会被插入直线完全覆盖，于是从集合剔除前驱，之后继续处理前驱。处理完前驱后以类似的方法处理后继，计算后继与插入直线的交点，如果交点在插入直线的起始作用点之前，那么插入直线就没有插入的意义，如果交点在后继的后继的起始作用点之后，后继就会被插入直线完全覆盖，剔除后继后，重复流程。 对于查询操作，我们对集合进行二分查找，找到所有起始作用点不大于$x_0$的直线中拥有最大起始作用点的那个函数$y$，此时$f(x_0)=y(x_0)$。

查询操作，很显然时间复杂度是二分查找的时间复杂度，为$O(\log_2n)$。

插入操作，我们可以让每个插入直线负责自己的整个生命周期，每个插入直线的生命周期仅为插入和删除两种，时间复杂度都是$O(\log2_n)$，因此插入操作的摊还时间复杂度可以认为是$O(\log_2n)$。

一些变种

大部分凸包技巧的问题都是给定直线$a_ix+b_i$，将其插入到集合中，以及动态询问所有直线在$x=x_0$的时候的最大值。

实现凸包技巧的方式一般是按照斜率对凸包进行排序，并计算相邻凸包的交点，从而找到每条直线的作用区间。

下面讲一些不是直接的凸包技巧，但是可以用相同技术来解决的问题。

考虑给定一颗$n$个顶点的带边权（边权为正数）的树，根顶点为$1$，以及两个长度为$n$的正整数序列$a$，$b$。记$A_i$表示顶点$i$的所有祖先结点，要求对于$2\leq i\leq n$，计算$\min_{j\in A_i\land a_j>b_i} \frac{dist(i,j)}{a_j-b_i}$，并输出。

提供一道题目。

首先我们可以记$d_i$表示顶点$i$的深度。这样对于固定的$i$，问题实际上要我们求$\min_{j\in A_i\land a_j>b_i} \frac{d_i-d_j}{a_j-b_i}$。

很显然这东西没法直接化成我们的仿射函数。我们可以稍加修改，将$d_i$替换成$x$，其余数视作常数，那么$\frac{d_i-d_j}{a_j-b_i}$实际上也是一个仿射函数：

\[\begin{aligned} y&=\frac{x-d_j}{a_j-b_i}\\ (a_j-b_i)y+d_j&=x \end{aligned}\]

这样我们得到了这些这些函数的逆，它们也是仿射函数，并且它们更加优秀。考虑$\frac{x-d_j}{a_j-b_i}$与$\frac{x-d_k}{a_k-b_i}$的交点，需要注意两条直线的交点唯一，并且它们有相同的$x$与$y$值，我们不直接算交点的$x$值，而是算交点$y$值：

\[\begin{aligned} (a_j-b_i)y+d_j&=(a_k-b_i)y+d_k\\ a_jy+d_j&=a_ky+d_k\\ y&=\frac{d_j-d_k}{a_k-a_j} \end{aligned}\]

可以发现两条直线的交点的$y$坐标与$i$无关。

我们可以将所有祖先结点建立一条直线$\frac{x-d_j}{a_j-t}$。其中$x,t$都是未知的，并且很显然对于相同的$t$，$a_j$越大，直线的斜率越小。因此我们可以对这些直线按照斜率排序。接下来再考虑如何确定它们的作用区间，我们可以用$y$来区分，由于斜率是正数，所以较小的$y$对应较小的$x$。现在的问题就非常类似凸包技巧了。

现在我们回到原来的问题。我们可以发现一条直线作用于所有子树中的顶点，而它们是一个区间，因此我们可以用线段树维护凸包集合，这里依旧存在一个问题，我们仅考虑哪些$a_j>b_i$的顶点，这里我们可以按照$a_j$的顺序处理插入，并按照$b_i$的顺序处理查询。这样时间复杂度为$O(n(\log_2n)^2)$。

并且实际上我们可以进一步优化到$O(n\log_2n)$时间复杂度，方式类似。问题等价于让让我们找到$\max_{j\in A_i\land a_j>b_i} \frac{a_j-b_i}{d_i-d_j}$。对应的如果我们选择$b_i=x$，那么可以发现两条直线的交点为$y=\frac{a_j-a_k}{d_k-d_j}$。这时候我们在树上dfs，可以发现$d_i$是递增的，这意味着我们只需要删除尾部一些直线而已，这里可以直接二分。而$a_j>b_i$这个要求其实可以忽略，因为它只会产出负数，是不会被考虑的。

李超线段树

我们稍微修改一下上一节的问题，这次我们插入的不是直线，而是线段。即插入的一阶多项式的作用域是某个有限区间而非全域。

这个问题我们就无法拿凸包技巧来解决。下面我们提供一个插入时间复杂度为$O((\log_2n+m)^2)$，查询复杂度为$O(\log_2n+m)$的解决方案。

首先，如果线段区间，查询的下标范围很大，我们可以先离散化，下面我们的分析将认为可能的作用域为${0,1,\ldots,O(n+m)}$。我们可以建立一个线段树，每个线段树结点维护的是一条线段。我们知道线段树结点包含区间的概念，而结点保存的线段必定是作用域覆盖了整个结点区间的线段。这种线段可能有很多，我们在每个结点仅保存其中的一个。

对于插入操作，我们按照线段树的规则进行递归更新。如果线段的作用域完整覆盖当前所在结点的区间，那么执行下面流程。如果结点还未保存任何线段，则记录线段，并结束。否则，我们就计算保存的线段和插入线段的交点。

如果交点处于区间中间的左侧，那么我们就将结点记录的线段更新为两条线段斜率较大者，之后对左子结点下传斜率较小者。否则，我们就将结点记录的线段更新为两条线段斜率较小者，对右子结点下传斜率较大者。一次线段树更新会涉及$O(\log_2n+m)$个结点，而每次下传到完整覆盖区间后，就仅单向下传最多$O(\log_2n+m)$次，因此更新的时间复杂度为$O((\log_2n+m)^2)$。

由于我们每次都会将插入直线下传到它可能的优势区间，因此优势区间包含$x_0$的线段一定记录在某个对于区间包含$x$的结点中。实际上如果这个线段没有记录在$[x,x]$对应的结点中，就意味着它没有下传，换言之保存在了$[x,x]$的某个祖先结点中。

对于查询操作，我们从上至下遍历所有区间覆盖$x_0$的结点，并计算它们保存的一阶多项式在该点的值中的最大值，由于包含$x_0$的区间最多有$O(\log_2n+m)$个，因此时间复杂度为$O(\log_2n+m)$。

提供一道BZOJ1007。

单调增斜率优化

首先让我们来考虑下面问题：

要求求解$f(n)$，其中$f$定义如下：

\[f(i)=\Bigg\{ \begin{array}{ccc} 0&,i=0\\ \min\{h(j)-s(i)s(j)|0\leq j <i\}&,i\ge 1 \end{array}\]

其中h是一个已知函数，而s是一个严格递增函数。这里我们简单记$r(j,i)=f(j)+h(j)-s(i)s(j)$。

可以很轻松地给出一个$O(n^2)$时间复杂度的算法，但是假如你学会了斜率优化，那就能将时间复杂度降低为$O(n)$。

假设存在$k<j<i$，且$r(j,i)\leq r(k,i)$，那么我们可以推得：

\[r(j,i) \leq r(k,i)\\ \Rightarrow h(j)-s(i)s(j) \leq h(k)-s(i)s(k)\\ \Rightarrow h(j)-h(k) \leq s(i)(s(j)-s(k))\\ \Rightarrow \frac{h(j)-h(k)}{s(j)-s(k)}\leq s(i)\]

看着上面公式是不是有点眼熟？让我们记Y(i)=h(i)，记X(i)=s(i)，那么带入上面公式得到：

\[r(j,i) \leq r(k,i)\\ \Rightarrow \frac{Y(j)-Y(k)}{X(j)-X(k)} \leq s(i)\]

这时候应该认出来了吧，这就是我们的斜率公式，即不等式的左边表示的是从$(X(k),Y(k))$出发到点$(X(j),Y(j))$的直线斜率。这里我们简单记$g(k,j)=\frac{Y(j)-Y(k)}{X(j)-X(k)}$。

注意我们两个公式是以等价的方式推导出来的，即$r(j,i)\leq r(k,i)$当且仅当$g(k,j)\leq s(i)$成立。

假设存在三个点$t<k<j<i$，且$g(t,k)\geq g(k,j)$，那么我们可以发现，如果$r(k,i)\leq r(t,i)$，这意味着$g(t,k)\leq s(i)$，但是考虑到$g(k,j) \leq g(t,k)$，因此可知$g(k,j)\leq s(i)$，从而推出$r(j,i) \leq r(k,i)$。换言之，$f(i)$永远拥有比$r(k,i)$更好的选择，因此我们可以在计算$f(i)$时不考虑$f(k)$。

由于之前推出的结论，我们发现真正需要被考虑的点$(X(i_1),Y(i_1)),(X(i_2),Y(i_2)),\ldots$，其必然有斜率递增的特性，即$g(i_{m-1},i_{m})\leq g(i_{m},i_{m+1})$。因此我们只需要利用一个双端队列维护一个斜率递增的点集，考虑到$s(i)$严格增的性质，我们就可以在$O(n)$的时间复杂度内计算$f(1),\ldots ,f(n)$。

凸包技巧的应用

区间凸包技巧

给定$n$条直线，第$i$条可以表示为$f_i(x)=a_ix+b_i$。现在给出$m$个请求，每个请求给定$l,r,x$，要求回答$\max_{l\leq i\leq r} f_i(x)$。其中$n,m\leq 10^5$

线段树可以直接解决，时间复杂度为$O(n\log_2n(\log_2m+\log_2n))$。

子树凸包技巧

给定一颗$n$个顶点的树，顶点$i$保存一条直线$f_i(x)=a_ix+b_i$。之后给出$m$个查询，第$i$个指定一个顶点$u_i$以及一个整数$x_i$，要求回答以$u$为根的子树中保存的所有直线在$x_i$处取值的最大值。

这个问题可以通过树上启发式合并解决。或者可以发现在树上做dfs序，那么子树实际上是一个区间，问题变成了区间凸包技巧问题。

路径斜率优化

给定一颗$n$个顶点的树，顶点$1$为根，每条边有边权，现在我们希望从每个顶点出发坐巴士前往顶点$1$，允许在任意站点换乘。假设从顶点$i$坐巴士出发，乘坐$x$公里，那么费用为$a_ix+b_i$。现在要求计算每个顶点出发到顶点$1$的最小费用。所有边权均为正数，且满足顶点$i$距离顶点$1$越远，则$a_i$越大。$n\leq 10^5$

可以发现我们实际上要在每个顶点处，维护所有祖先顶点信息组成的一个凸包。但是难点在于凸包不支持删除操作。

这里有两种做法，第一种就是发现凸包的新增和删除是栈式操作，这意味着我们可以利用持久化数据结构避免删除操作（不带路径压缩的并查集也可以利用这个技术实现持久化）。这样我们可以利用$O(n\log_2n)$的时空复杂度解决这个问题。

还有一种很神奇的方式。注意到从根到任意顶点路径上，$a$属性是严格递增的，因此我们可以利用斜率优化代替凸包技巧。那么斜率优化对比凸包技巧的有点是啥？斜率优化的修改操作只会修改$O(1)$的数据，即一次斜率优化，我们会修改队列头部，队列尾部，以及队列尾部的元素，只有3个信息。因此我们很容易对其实现恢复操作。但是斜率优化的时间复杂度是摊还的，其在序列上拥有正确的$O(n)$时间复杂度，但是在树形结构上时间复杂度会劣化到$O(n^2)$。但是由于队列中保存的顶点满足斜率递增的性质，因此我们可以用二分来快速寻找新的队头和队尾，这样就能保证时间复杂度为$O(n\log_2n)$。

提供一道原题。

路径凸包技巧

给定一颗$n$个顶点的树，顶点$1$为根，每条边有边权，现在我们希望从每个顶点出发坐巴士前往顶点$1$，允许在任意站点换乘。假设从顶点$i$坐巴士出发，乘坐$x$公里，那么费用为$a_ix+b_i$，且从$i$顶点出发的巴士的终点站在$e_i$，即不能一次性从$i$到达$e_i$的祖先。现在要求计算每个顶点出发到顶点$1$的最小费用。所有边权均为正数。$n\leq 10^5$

这道题和路径斜率优化题目的区别在于，不保证离根越远的顶点的$a_i$越大，因此在这里斜率优化是不适用的。我们必须借助凸包技巧，但是这里也不能利用持久化技术，因为持久化必须保证删除是栈式的。

我们可以利用点分治解决这个问题（想不到吧）。假设我们在处理一颗子树$T$，我们首先搜出重心，如果重心不是子树中所有顶点的祖先，那么重心的所有祖先一定存在于某颗重心下的子树$S$中，我们将这个$S$先用点分治递归处理掉（点分治对子树的执行顺序没有要求），这个不会影响时间复杂度。之后我们将重心的DP直接暴力求出（仅考虑$S$对重心顶点DP的贡献），这一步时间复杂度不超过$|S|$，因此也不会影响总的时间复杂度。之后我们将重心下其余子树（除了$S$）中的所有顶点全部取出，按照其可以访问到的祖先顶点的深度进行排序，之后我们不断将$S$中的重心祖先加入到动态凸包中，同时不断计算对其余顶点的贡献，这一步的时间复杂度为$|T|\log_2|T|$。

这样我们最后就能得出结果，总的时间复杂度为$O(n(\log_2n)^2)$。

离线动态凸包技巧

处理$n$个请求，请求分三类。第一类：给定$a,b$，插入一条直线$y=ax+b$；第二类：删除第$i$次操作插入的直线；第三类，给定某个$x$，查询当前所有直线在$x$处最大值。其中$n\leq 10^5$。

整个问题唯一的难点就是支持删除上面。这里我们可以使用和利用线段树使并查集支持删除相同的技术。建立一个线段树，线段树的区间$[l,r]$表示在第$l$次请求到第$r$次请求之间存在的所有直线。

对于插入操作，我们可以通过离线确认这个直线删除的时间（如果永远不删除，那么把删除时间设置为$n+1$）。记时间$l$为当前请求编号（请求时间），$r+1$为删除时间，那么我们就将这条直线插入到线段树的区间$[l,r]$中。线段树每个结点中维护一个凸包技巧，由于凸包不支持上推操作，因此这里我们也不下压脏标记，只是在每次查询的时候，路径中的所有顶点中维护的凸包技巧都对结果进行贡献即可。

删除操作于是乎就嗖的一下，不见了。

每次操作最多修改$\log_2n$个顶点中维护的凸包技巧，或者查询$\log_2n$个顶点中的凸包技巧，因此每个操作的时间复杂度均为$O((\log_2n)^2)$。

二维凸包

一个多边形，如果任意两个顶点之间连线上所有点都落在多边形内，则称这个多边形为凸包。

给定$n$个点，其中至少有三个点不共线，我们可以通过Graham scan算法在$O(n\log_2n)$的时间复杂度内计算凸包。如果只需要求上下凸包，也可以直接利用凸包技巧$O(n\log_2n)$求。

对于一个上凸包，第$(x_i,y_i)$为从左往右数第$i$个凸包上的顶点，则一定有$2y_i>y_{i-1}+y_{i+1}$。而对于一个下凸包，则正好相反，有$2y_i<y_{i-1}+y_{i+1}$。

题目1：给定$n$个顶点，要求计算最远的两个顶点的距离

不难发现，最远的两个顶点一定在凸包上，且一定是凸包的顶点。因此可以先$O(n\log_2n)$搞出凸包。但是如果数据设计的就是给定的$n$个点恰好就是凸包上的顶点，那么接下来的暴力枚举还是需要$O(n^2)$的时间复杂度。

这里我们可以使用另外一种技术，叫做旋转卡壳算法，就是维护两个平行线，分别切凸包上下两个顶点，且不停旋转。可以发现最远的两个顶点一定在两个平行线于凸包的切点处。而切点总数为$O(n)$，因此总的时间复杂度为$O(n)$。

题目2：给定$n$个数$a_1,a_2,\ldots,a_n$，要求输出另外一个序列$b_1,\ldots,b_n$，其中满足$b_1=a_1,b_n=a_n$，而对于任意$1<i<n$，需要满足$b_i=\max(a_i,\frac{b_{i-1}+b_{i+1}}{2})$。如果有多个序列，则输出任意一个即可。

容易发现如果我们将每个数$a_i$看作一个顶点$(i,a_i)$，并在这些顶点上建立一个上凸包，那么可以直接取$b_i$为凸包上边界中坐标为$i$处的高度。可以发现这样得到的$b_i$一定满足条件（由于是上凸包，因此$b_i\geq a_i$是一定成立的，且上凸包保证了$b_i\geq \frac{b_{i-1}+b_{i+1}}{2}$）。

事实上我们还能证明解是唯一的。假设还有一组解，记作$c_1,\ldots,c_n$，满足$c_i=\max(c_i,\frac{c_{i-1}+c_{i+1}}{2})$，且$b\neq c$。我们设对于任意$j<i$，有$b_j=c_j$，且$b_i\neq c_i$。不失一般性可以认为$c_i>b_i$（否则我们可以交换$c$和$b$），那么很显然$c_i>a_i$，且$c_{i+1}-c_i=c_i-c_{i-1}$可以知道$(i,c_i)$与$(i-1,c_{i-1})$，$(i+1,c_{i+1})$共线。记$(k,c_k)$为最后一个与$(i-1,c_{i-1})$和$(i,c_i)$共线的顶点，则一定有$c_k\leq b_k$，但是由于$(k,b_k)$处于上凸包上，因此$c_k\leq b_k$是不可能满足的。即对于任意顶点$k\geq i$，都应该有$c_k>b_k$，这与$c_n=b_n=a_n$相悖，因此假设不成立。至此我们证明了解的唯一性。

由于凸包上的顶点已经按照横坐标排好序了，因此可以直接用个栈直接算出整个凸包，时间复杂度为$O(n)$。

最小斜率和最大斜率和最小斜率绝对值

题目1：给定$n$个不重复的点$(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$，且这$n$个点的$x$值都不同。要求找到其中两个斜率最大的点。

由于每个点的$x$值不同，我们可以按照$x$值进行排序，现在默认所有点都按照斜率排过序了。之后我们考虑三个点$p_i=(x_i,y_i),p_j=(x_j,y_j),p_k=(x_k,y_k)$，其中$x_i<x_j<x_k$。可以发现如果$p_j$在$p_i$和$p_k$的连线上方的话，这时候$p_i,p_j$的斜率不小于$p_i$和$p_k$，同样的如果如果$p_j$在$p_i$和$p_k$的连线下方的话，这时候$p_j,p_k$的斜率不小于$p_i$和$p_k$。

因此我们只需要考虑所有$x$值邻近的点。总的时间复杂度为$O(n\log_2n)$。

提供一道问题。

题目2：给定$n$个不重复的点$(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$，且这$n$个点的$x$值都不同。要求找到其中两个斜率最小的点。

将所有$y$值取反，这时候斜率最小问题便变成了斜率最大问题，等价于问题$1$。实际上，可以发现可能的斜率最小的点对出现在$x$值相邻的点对之间。

题目3：给定$n$个不重复的点$(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$，且这$n$个点的$x$值都不同。要求找到其中两个斜率最小的点。

考虑将所有点按照$y$进行排序。假如存在多个点的$y$值相同，那么我们可以直接得到结果，最小的斜率绝对值为$0$。否则，我们考虑三个点$p_i=(x_i,y_i),p_j=(x_j,y_j),p_k=(x_k,y_k)$，其中$y_i<y_j<y_k$。可以发现$y_i,y_k$的斜率绝对值始终不小于$y_i,y_j$和$y_j,y_k$中的最小值。

因此我们只需要考虑所有$y$值邻近的点。总的时间复杂度为$O(n\log_2n)$。

SRM787 div1第一题。

参考资料