hdu 4347 The Closest M Points (kd-tree+优先队列,求M近邻)

2017年10月9日 0 作者 CrazyKK

题目链接

题意:

给出若干个点,在给出一个定点,求距离该定点最近的m个点。

思路:

我们已经知道kd-tree可以得到最近邻,实际上M近邻,只需要维护一个size为M的优先队列就可以了。

需要注意,优先队列的元素一定要先定义小于关系orz

以及这次采用了轮盘转的策略划分维度,也就是按照深度,所有维度轮流作为split-method(实际用起来效果还是挺棒的orz