计算几何

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\mod 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统计即可。

一道不错的类似题目

求三角形内心坐标

问题:在圆心为原点,半径为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$,要求找到一组非负未知数$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}^nx_i$,输出任意一组可行解。其中$n\leq 10^5$,结果允许是浮点数。

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

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

集群中心问题

题目1:给定$n$个二维平面点$(x_1,y_1),\ldots,(x_n,y_n)$,要求找到一个中心$(a,b)$,满足所有点到中心的曼哈顿距离之和最小。

由于是曼哈顿距离,所有不同的维度可以分别计算。

现在的问题变成了有$n$个数值$x_1,\ldots,x_n$,找一个中心值$a$,满足$\sum_{i=1}^n|x_i-a|$最小。这里我们直接取$a$为$x$的中间数即可。

题目2:在一个无穷大的棋盘上,给定$n$个网格点$(x_1,y_1),\ldots,(x_n,y_n)$,这些网格内放置了棋子。之后我们要将这些网格点移到到一块,即所有棋子占用的行恰好为连续的$n$行,而所有棋子占据的列恰好是连续的$n$列。每次移动棋子,可以将其移动到有公共边的网格中。问最少需要的移动次数。

这里我们可以把行和列拆开来计算。现在的问题是存在$n$个整数$x_1,\ldots,x_n$,很显然在移动的时候不会改变这些整数的顺序。要求找一个整数$a$(与$x_1-1$对齐),满足$\sum_{i=1}^n|x_i-(a+i)|$最小。我们修正一下公式可以发现为$\sum_{i=1}^n|(x_i-i)-a|$,因此$a$实际上是$x_1-1,x_2-2,\ldots,x_n-n$的中位数。

提供一道题目SRM 795 div1的第二题。

题目3:给定$n$个二维平面点$(x_1,y_1),\ldots,(x_n,y_n)$,要求找到一个中心$(a,b)$,满足所有点到中心的2范数距离之和$J(a,b)=\sum_{i=1}^n(a-x_i)^2+(b-y_i)^2$最小。

考虑偏导数:

\[\frac{\partial}{\partial a}J(a,b)=2\sum_{i=1}^n(a-x_i)\]

由于极值点在偏导数为$0$的时候取到,因此有:

\[\begin{aligned} &2\sum_{i=1}^n(a-x_i)=0\\ \Rightarrow &na=\sum_{i=1}^nx_i\\ \Rightarrow &a=\frac{1}{n}\sum_{i=1}^nx_i \end{aligned}\]

同样有$b=\sum_{i=1}^ny_i$。

题目4:给定$n$个二维平面点$(x_1,y_1),\ldots,(x_n,y_n)$,要求找到一个中心$(a,b)$,满足所有点到中心的欧几里德距离之和$J(a,b)=\sum_{i=1}^n\sqrt{(a-x_i)^2+(b-y_i)^2}$最小。

可以证明函数$J$是凸函数,因此可以上三分套三分,梯度下降,模拟退火啥的。

凸函数的证明

集群问题

题目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$条。
  • 欧几里德最小生成树是三角化后所有三角形的边的子集。
  • 所有三角形的外切圆内(圆周上不算),都不会包含其余顶点。
  • 对于任意顶点,距离它的最近点一定在三角化后与它拥有公共边。

一道题目

参考资料