P1429 平面最近点对（加强版）

题目

题目描述 给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的

输入输出格式 输入格式： 第一行：n；2≤n≤200000

接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。

输出格式： 仅一行，一个实数，表示最短距离，精确到小数点后面4位。

输入输出样例 输入样例#1： 3 1 1 1 2 2 2 输出样例#1： 1.0000

思路

• 首先考虑暴力，枚举所有点对，复杂度为O(N^2)

• 然后就是正解：

  分治算法

  • 每一次把平面分成两个部分，找出左边的最近点对，右边的最近点对以及穿越分割线的最近点对。
  • 在求穿越分割线的最近点对时，用左右已经算出的最小值作为参考，一旦大于就停止搜索