算法合集之《计算几何学》

For personal use only in study and research; not for commercial use

发言稿

芇

莅 计算几何学是研究几何问题的算法，在现代工程学与数学，诸

如计算机图形学、计算机辅助设计、机器人学都要应用计算几何学，在信息学竞赛中几何题也开始出现了，但是在实际的竞赛中，几何题得分率往往是最低的，所以我对几何题的算法进行了一下探索

肁任何复杂的算法都是由许多简单的算法组合而成的，计算几何

题也同样如此，先来看最基本的算法： 1、

2、蝿求直线的斜率 3、

4、肆求2条直线的交点 5、

6、蒅判断2条线段是否相交 7、

8、蒂求叉积等等。

芇这些都是最基本的算法，是解几何题的基础，任何对基本算法

的不熟悉，都可能导致解题的失败，所以熟悉几何题中的基本算法是非常重要的。

袅但是有了基本算法是远远不够的，因为光靠竞赛时的临时思考，

组合算法从时间上来说是来不及的，这就需要熟悉一些经典算法，在竞赛中直接使用，比如： 1、 2、薅求凸包 3、

4、袃求最近点对 5、

6、罿判断点是否在多边形内等等

袈 基本算法和经典算法都是比较简单的，最后我们再来说一下几

何题的题型及解几何题的一些技巧，

蚄几何题的几种类型

1、 2、

蚁羀纯粹的计算求解题

解这一类题除了需要有扎实的解析几何的基础，还要全面地看

待问题，仔细地分析题目中的特殊情况，比如求直线的斜率时，直线的斜率为无穷大，求2条直线的交点时，2直线平行，等等。这些都是要靠平时学习时的积累。 3、 4、

螄蚇存在性问题

这一类问题可以用计算的方法来直接求解，如果求得了可行解，

则说明是存在的，否则就是不存在的，但是模型的效率同模型的抽象化程度有关，模型的抽象化程度越高，它的效率也就越高，几何模型的的抽象化程度是非常低的，而且存在性问题一般在一个测试点上有好几组测试数据，几何模型的效率显然是远远不能满足要求的，这就需要对几何模型进行一定的变换，转换成高效率的模型，下面就通过一个例子来对这种方法进行一下阐述。 5、 6、

腿莁求几何中的最佳值问题

这类问题是几何题中比较难的问题，一般没有什么非常有效的

算法能够求得最佳解，最常用的是用近似算法去逼近最佳解，近似算法的优劣也完全取决于得出的解与最优解的近似程度。

莆[例1]游戏者B在一张100*100纸上确定了一个目标点，游戏者A

一开始在点(0,0)上，每次游戏者A从一个点到另一个点，如果新的点

离目标点近了，那么游戏者B说“Hotter”，如果新的点离目标远了，那么游戏者B说“Colder”，如果距离不变，那么游戏者B说“Same”。

袄 输入文件包括很多行，每行包含游戏者A这一步到达的点(x,y)

和游戏者B说的话，对每次游戏者B说话，判断目标点可能的位置的面积，精确到小数点后2位。

螂这是一道纯粹的计算求解题，首先证明可能的位置的图形一定

是个凸多边形。

袁因为每次对游戏者B的回答，就可以确定可能的位置在出发点

和到达点中垂线的哪一边或就是中垂线，每次的可能图形都是凸多边形。所以这个图形是许多个凸多边形的交集，所以这个图形是凸多边形。

膅接下来就是解题了，先令多边形为一个四边形，(0,0),(0,100),

(100,100),(100,0)，然后对每次游戏者B的回答，用这条中垂线将多边形分成2部分，取可能的那部分，即可。

羄不过这样并不是完全正确的，必须考虑到特殊情况，比如游戏

者A到达的点和这步前的点完全相同，这时就不存在中垂线了，这些都是解题中要注意的重点。

膃在这道题中就用到了很多解析集合的知识，包括求线段之间的

交点，判断点是否在线段的两边，证明最终图形是凸多边形等等。

芈[例2]在一个无限长的条形路上，

膈有n(n<=200)个柱子，体积不计，

羄有一个人想从左边走到右边，人

艿近似看成一个半径为R的圆（如右图），

肀问能否实现。

羆拿到这道题最基本的做法是对从最左边的柱子到最右边的柱子

中，每一个竖列进行扫描，计算可走到的范围，如果到最右边的柱子所在的列都有可走到的范围，则有解，否则无解。可是如果最左和最右的2个柱子相距非常远，那么这样计算的时间复杂度无疑是非常高的，所以我们应该对这个几何模型进行转化。

肄首先在这个图形中，不动的是柱子（近似看成点），动的是人（近

似看成一个圆），这样处理比较麻烦，所以我们应该先把动的转换成

本文来源：https://www.bwwdw.com/article/7xgd.html