#1580. 最近点对距离问题
最近点对距离问题
题目描述
在应用中,常用诸如点、圆等简单的几何对象代表现实生活中的实体。在涉及这些几何问题时,常需要了解其邻域中其它几何对象的信息。例如,在空中交通控制问题中,若将飞机作为空间中移动的一个点来看,则具有最大碰撞危险的架飞机,就是这个空中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。 最接近点对问题的提法是:给定平面上个点,找其中的一对点,使得在个点对中,该点对的距离最小。严格地说,最接近点对可能多于一对。为了简单起见,这里只限于找一对。(预备知识:在平面几何中每一个点都用来表示它在平面中的位置,点与点之间的距离可用公式:
输入格式
平面中各点的坐标,以表示输入结束。(点的个数不超过
输出格式
距离最近的两点坐标(格式见样例)。
样例
输入样例
7 2
2 7
3 4
9 7
0 0
输出样例
3.16