计算几何

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)转换为(x+y2,x−y2)，之后计算各个点之间的曼哈顿距离，那么就可以得到原平面的切比雪夫距离。

题目1：给定n个二维点(x1,y1),…,(xn,yn)，现在要求找到一个中心(x,y)，要求最小化所有二维点到中心的最大曼哈顿距离。即记f(x,y)=maxi|xi−x|+|yi−y|，要求找到minx,yf(x,y)。其中n≤105，且0≤xi,yi≤1018

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

三维情况

问题1：给定n个三维整数点(x1,y1,z1),…,(xn,yn,zn)，现在要找到一个整数中心(x,y,z)，要求最小化所有点到中心的最大曼哈顿距离。即记f(x,y,z)=maxi|xi−x|+|yi−y|+|zi−z|，要求找到minx,y,zf(x,y,z)。其中n≤105，且0≤xi,yi≤1018

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

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

…≤x+y+z≤……≤−x+y+z≤……≤x−y+z≤……≤x+y−z≤…

我们引入一些新的变量：

{a=−x+y+zb=x−y+zc=x+y−z

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

…≤a+b+c≤……≤a≤……≤b≤……≤c≤…

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

下面我们考虑整数带来的影响，由于(x,y,z)都是整数，而x=b+c2，y=a+c2，z=a+b2。因此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第一题。

参考资料