蛮力法

最近点对问题要求在一个包含n个点的集合中，找出距离最近的两个点。

为了简单起见，我们只考虑最近对问题的二维版本。假设所讨论的点是以标准笛卡儿 坐标形式 \((x_i, y_i)\) 给出的，两个点 \(p_i=(x_i, y_i)\) 和 \(p_j=(x_j, y_j)\) 之间的距离是标准的欧几里得距离。

很显然，求解该问题的蛮力算法应该是这样：分别计算每一对点之间的距离，然后找 出距离最小的那一对。当然，我们不希望对同一对点计算两次距离。为了避免这种状况， 我们只考虑 \(i<j\) 的那些对 \((p_i, p_j)\)。

凸包问题是在平面或者高维空间的一个给定点集合中寻找凸包。

凸集合定义如下：

+ 定义 对于平面上的一个点集合（有限的或无限的），如果以集合中任意两点 \(p\) 和 \(q\) 为 端点的线段都属于该集合，我们说这个集合是凸的。

对于平面上 \(n\) 个点的集合，它的凸包就是包含所有这些点（或者在内部，或者在边界上）的最小凸多边形。

对于一个 \(n\) 个点集合中的两个点 \(p_i\) 和 \(p_j\)，当且仅当该集合中的其他点都位于穿过这两点的直线的同一边时，它们的连线是该集合凸包边界的一部分对每一对点都做一遍检验之后，满足条件的线段构成了该凸包的边界。

为了实现这个算法，需要用到一些解析几何的基本知识。首先，在坐标平面上穿过两个点 \((x_1, y_1)\)，\((x_2, y_2)\)的直线是由下列方程定义的：

其中 \(a=y_2-y_1\)、\(b=x_1-x_2\)、\(c=x_1y_2-y_1x_2\)。

其次，这样一根直线把平面分为两个半平面：其中一个半平面中的点都满足 \(ax+by>c\)，而另一个半平面中的点都满足 \(ax+by<c\)（当然，对于线上的点来说，\(ax+by=c\)）。因此，为了检验某些点是否位于这条直线的同一边，只需把每个点代入 \(ax+by=c\)。