#1580. 最近点对距离问题

最近点对距离问题

题目描述

在应用中,常用诸如点、圆等简单的几何对象代表现实生活中的实体。在涉及这些几何问题时,常需要了解其邻域中其它几何对象的信息。例如,在空中交通控制问题中,若将飞机作为空间中移动的一个点来看,则具有最大碰撞危险的2\red{2}架飞机,就是这个空中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。 最接近点对问题的提法是:给定平面上N\red{N}个点,找其中的一对点,使得在N\red{N}个点对中,该点对的距离最小。严格地说,最接近点对可能多于一对。为了简单起见,这里只限于找一对。(预备知识:在平面几何中每一个点都用x,y\red{(x,y)}来表示它在平面中的位置,点1x1,y1\red{1(x_{1},y_{1})}与点(x2,y2)\red{(x_{2},y_{2})}之间的距离可用公式:

dist=(x1x2)2+(y1y2)2\red{dist=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}}

输入格式

平面中各点的坐标,以00\red{(0,0)}表示输入结束。(点的个数不超过60000)\red{60000)}

输出格式

距离最近的两点坐标(格式见样例)。

样例

输入样例

7 2
2 7
3 4
9 7
0 0

输出样例

3.16