凸包-最近点对

NOIP提⾼组CSP-S复赛需掌握的算法

1、排序算法（快排、选择、冒泡、堆排序、⼆叉排序树、桶排序）

2、DFS/BFS 也就是搜索算法，剪枝务必要学！ 学宽搜的时候学⼀下哈希表!

3、树

①遍历

②⼆叉树

③⼆叉排序树（查找、⽣成、删除）

④堆（⼆叉堆、左偏树、堆排序）

⑤Trie树4、图（图论建模）

①最⼩⽣成树

②最短路径

③计算图的传递闭包

④连通分量（其中要掌握并查集技术）

强连通分量tarjin⑤拓扑排序、关键路径

⑥哈密尔顿环

⑦欧拉回路（USACO 3.3 题1 Fence）

⑧Bell-man Ford、SPFA（能解决负权回路）（USACO 3.2 题6 Butter）

⑨⼆分图（匈⽛利算法）(USACO 4.2 题2 stall)5、动态规划（背包问题只是其中⼀种）

①线性动规

②区间动规

③树形动规

④图形动规6、分治（掌握了动规分治就好学了）

7、贪⼼

8、位运算（可以⽤来进⾏优化）

——————————————————————————————————————————————————————————————————————————————————————

补充：

时间复杂度（渐近时间复杂度的严格定义，NP问题，时间复杂度的分析⽅法，主定理）

排序算法（平⽅排序算法的应⽤，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序）

数论（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余⽅程，中国剩余定理）

指针（链表，搜索判重，邻接表，开散列，⼆叉树的表⽰，多叉树的表⽰）

按位运算（and，or，xor，shl，shr，⼀些应⽤）

图论（图论模型的建⽴，平⾯图，欧拉公式与五⾊定理，求强连通分量，求割点和桥，欧拉回路，AOV问题，AOE问题，最⼩⽣成树的三种算法，最短路的三种算法，标号法，差分约束系统，验

证⼆分图，Konig定理，匈⽛利算法，KM算法，稳定婚姻系统，最⼤流算法，最⼩割最⼤流定理，最⼩费⽤最⼤流算法）

凸包算法及凸包融合

凸包算法是计算凸包的一种常用算法，它可以找到一组点集中最外层的凸多边形。凸包融合是指将两个凸包合并成一个新的凸包，能够通过减少顶点数目来优化计算效率。

凸包算法主要有以下几种常见的实现方法：

1.枚举算法：对于点集中的每一对点，判断其他点是否位于这两点所确定的直线的一侧。如果所有点都在一侧，则这两点是凸包上的边。时间复杂度为O(n^3)。

2. Graham扫描算法：选取一个点作为基准点，将其他点按照相对于基准点的极角大小进行排序。然后依次处理每个点，判断其是否属于凸包。时间复杂度为O(nlogn)。

3. Jarvis步进算法（也称为包裹法）：从点集中选取一个临时点p，然后找到与p相邻的点集中极角最小的点q，将q加入凸包中。然后将q作为新的临时点p，重复以上步骤，直到回到第一个点。时间复杂度为O(nh)，其中h是凸包的边数。 4.快速凸包算法：通过空间分割和递归的方法进行凸包计算，时间复杂度为O(nlogn)。

凸包融合是指将两个凸包合并成一个新的凸包，通常需要满足以下条件：

1.相交边的共享：两个凸包如果相交，那么它们的公共边必须都在新的凸包中。

2.外部边的合并：如果两个凸包没有相交，那么合并后的凸包应该包含两个凸包的外部边。

3.顺序性：合并后的凸包应该按照某种规定的顺序进行连接。

凸包融合算法的一种常见方法是基于边的融合。具体步骤如下：

1.找到两个凸包之间的最近边，并将其作为起始边。

2.沿着其中一个凸包的边界向对面的凸包前进，每次选取与当前边最接近的边。

3.如果新选取的边与已经选取的边形成了一个角度大于180度的三角形，那么停止前进，并将新选取的边作为起始边。 4.重复步骤2和步骤3，直到回到起始边。

凸包融合算法可以减少凸包的顶点数量，从而提高计算效率。例如，对于两个有m和n个顶点的凸包，假设m > n，则融合后的凸包最多有m+n个顶点，而不是m*n个顶点。融合后的凸包可以保留原始凸包的边界信息，并且减少了计算和存储开销。

凸包算法详解

凸包算法是解决最小生成树问题的一种有效算法，它可以在不生成

环的情况下找到树的最好构造。在计算机科学中，最小生成树问题

是广义图论中的一个经典问题，它涉及到如何在给定一个有向图中

找到一个最小生成树。生成树是指保留图中所有节点，但只保留足

以生成该节点的所有边的集合。

凸包算法详解主要从两个方面进行阐述：算法原理和实现过程。

一、算法原理

凸包算法的基本思想是首先找到一个凸多面体，将该多面体内部的

所有点都看作是图中的节点，然后将这些节点按照某种次序连接起

来，生成树的每个节点都连接到至少一个凸多面体内部。具体实现

过程中，凸包算法会根据给定的有向图，找到一个凸多面体，将图

中的每个节点都映射到该多面体内部的一个点，然后将这些点连接

起来，生成树的每个节点都连接到至少一个凸多面体内部。凸包算法的时间复杂度为$O(n+m)$，其中$n$是图的节点数，

$m$是图的边数。这个时间复杂度可以通过递归的方式计算，也可

以使用静态数据结构来存储。

二、实现过程

1.选择一个凸多面体

在凸包算法中，我们需要找到一个凸多面体，使得该多面体内部的

所有点都适合作为图中的节点。具体实现过程中，可以使用任意一

种搜索算法，如深度优先搜索（DFS）或广度优先搜索（BFS）来枚

举所有的凸多面体。在搜索的过程中，我们需要记录每个凸多面体

的边数，以及该多面体内部的所有节点。

2.将节点连接起来

在凸包算法中，我们需要将图中的节点连接起来，以生成树的每个

节点都连接到至少一个凸多面体内部。具体实现过程中，可以按照

以下步骤将节点连接起来：（1）对于图中的每个节点，找到它所属的凸多面体，并将该节点连

接到该凸多面体内部。

（2）对于图中的每个节点，找到它所属的凸多面体内部的一个点，

并将该点与该节点连接起来。

（3）对于图中的每个节点，找到它所属的凸多面体内部的一个点，

并将该点与该节点连接起来。

3.递归搜索凸多面体

在凸包算法中，我们需要递归地搜索所有的凸多面体，以找到符合

1 / 6

课程名称：空间分析

指导老师：李 斌

班 号：

学 号：

姓 名：

2 / 6

凸包的建立算法

地测学院 杨博

1.凸包：

凸包概念:点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。

一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，这就是凸包了。

凸包可以使所有点在一定范围内，便于空间分析。

2.算法框图：

算法基本过程：

（1）鼠标输入点，并将各点坐标记录到数组p[]中

（2）寻找y坐标最小点p[i]，并与p[0]互换坐标值（这样保证了画凸包点从最下面点开始，且点位不丢失）

（3）分别将p[0]，p[1]赋给c[0]，c[1]（数组c[]存放凸包点坐标）

（4）利用向量公式R=(c[t-1]-p[i])*(c[t]-p[i])计算R值，以此来判断左右旋如下图是右旋

，若右旋或共线c[++t]=p[i]，i++，若为左旋c[t]=p[i]，i++。（r>0:p1在矢量p2p0的逆时针方向； r=0：p0p2p1三点共线； r<0:p1在矢量p2p0的顺时针方向， 即r>0 左

3 / 6

旋, <0 右旋, =0共线）

（5）i

（6）重复调用画线程序连线c[i]到c[i-1]直到i

（7）完成凸包绘图

鼠标点击输入点同时将点记入数组p[]中将p[]中y值最小点p[i]与p[0]点互换（即找出y值最小点）将p[]第一、二点赋予数组c[]第一、二点左旋是,R>0c[t]=p[i]i++t=0,1…,i=2,3...用向量计算R=(c[t-1]-p[i])*(c[t]-p[i])的叉积以此确定p[i]与c[t-1]-c[t]左右旋关系t++c[t]=p[i]i++否,R<=0i