本文共 591 字，大约阅读时间需要 1 分钟。

这一课我们介绍一个计算几何方面的穷举类算法问题。计算几何类的问题也是算法问题中的一个大的分类，并且在很多其他算法中都会用到一些几何公式，比如三角形剖分问题中如果是按照三角形的面积做最优剖分，则需要用到根据三角形的边长求面积的海伦公式。这一课我们用到的几何内容不多，只用到了求直线斜率的公式，主要还是为了演示穷举法的应用；同时还会介绍到一个用一遍扫描统计出有序序列中哪个值出现次数最多的代码技巧和快速排序在实际问题中的应用方法。

问题的提出

一个几何平面上有 N 个点，根据欧氏（欧几里得）几何原理，每两个点可以连成一条直线，N 个点可以连成很多条直线。当然，也会有多个点共线的情况出现，现在我们的问题是，在这 N 个点中，找出哪两个点组成的直线上包含最多的点，也就是找出含有最多点的那条直线。

图（1）多点共线问题示意图

如图（1）所示，在这么多直线中，绿色标识的那条直线包含了四个点，是包含最多点的直线。算法比赛中这个题目给出所有点的坐标，要求算法只输出包含最多点的那条直线上所包含的点的个数即可，所以最后的结果只是算法实现上复杂一点，数据模型其实非常简单。我们课程的主要目的是演示算法的分析、数据模型构建和编程实现算法的过程，以及在这个过程中分析和思考问题的方法，所以，我们修改一下题目要求。首先为每个点增加一个编号，然后要求在输出信息时，输出最多共线点的个数以及这些点的信息࿰

转载地址：http://gdcgj.baihongyu.com/