快速找点_趣味题目收集

快速找点

题目:在一个直角坐标线中,有10万个点,现在给出一个坐标(x,y),快速的找出离这个坐标最近的3个点。

思路一:计算出所有点与这个坐标(x,y)的距离,再排序,取出前三个。

思路二:以(x,y)为中心不断向外画正方形,正方形的面积增量,通过点的密度及一个修正值决定。在找到超过3个点时,调用思路一中的方法。

本来想画圆来着,但是仔细考虑了一下,计算距离需要平方相加再开方,还不如直接比较xy值的大小。另外也考虑过了二分法确定面积增量,但是考虑到遍历的次数会太多,就放弃了。

(有空研究一下)代码待写:

题目摘录于:http://www.cnblogs.com/fantong/archive/2013/05/11/3072764.html

原文地址:https://www.cnblogs.com/gaoquanning/p/3072785.html