发言稿 计算几何学是研究几何问题的算法，在现代工程学与数学，诸如计算机图形学、计算机辅助设计、机器人学都要应用计算几何学，在信息学竞赛中几何题也开始出现了，但是在实际的竞赛中，几何题得分率往往是最低的，所以我对几何题的算法进行了一下探索 任何复杂的算法都是由许多简单的算法组合而成的，计算几何题也同样如此，先来看最基本的算法： 1 、求直线的斜率 2 、求 2 条直线的交点 3 、判断 2 条线段是否相交 4 、求叉积等等。 这些都是最基本的算法，是解几何题的基础，任何对基本算法的不熟悉，都可能导致解题的失败，所以熟悉几何题中的基本算法是非常重要的。 但是有了基本算法是远远不够的，因为光靠竞赛时的临时思考，组合算法从时间上来说是来不及的，这就需要熟悉一些经典算法，在竞赛中直接使用，比如： 1 、求凸包 2 、求最近点对 3 、判断点是否在多边形内等等 基本算法和经典算法都是比较简单的，最后我们再来说一下几何题的题型及解几何题的一些技巧， 几何题的几种类型 1、 纯粹的计算求解题 解这一类题除了需要有扎实的解析几何的基础，还要全面地看待问题，仔细地分析题目中的特殊情况，比如求直线的斜率时，直线的斜率为无穷大，求 2 条直线的交点时，2 直线平行，等等。这些都是要靠平时学习时的积累。 2、 存在性问题 这一类问题可以用计算的方法来直接求解，如果求得了可行解，则说明是存在的，否则就是不存在的，但是模型的效率同模型的抽象化程度有关，模型的抽象化程度越高，它的效率也就越高，几何模型的的抽象化程度是非常低的，而且存在性问题一般在一个测试点上有好几组测试数据，几何模型的效率显然是远远不能满足要求的，这就需要对几何模型进行一定的变换，转换成高效率的模型，下面就通过一个例子来对这种方法进行一下阐述。 3、 求几何中的最佳值问题 这类问题是几何题中比较难的问题，一般没有什么非常有效的算法能够求得最佳解，最常用的是用近似算法去逼近最佳解，近似算法的优劣也完全取决于得出的解与最优解的近似程度。 [例1]游戏者B 在一张100*100 纸上确定了一个目标点，游戏者A 一开始在点(0,0)上，每次游戏者A 从一个点到另一个点，如果新的点离目标点近了，那么游戏者B 说“Hotter”，如果新的点离目标远了，那么游戏者B 说“Colder”，如果距离不变，那么游戏者B 说“Same”。 输入文件包括很多行，每行包含游戏者A 这一步到达的点(x ,y )...
