s*******k
发帖数: 227 | 1 【 以下文字转载自 CS 讨论区 】
发信人: stonerock (rock), 信区: CS
标 题: 算法问题
发信站: BBS 未名空间站 (Sat Jul 2 00:35:17 2011, 美东)
平面上有N个点,给你其中一个点p和半径r,怎么最快找到哪些点落在以p为中心r为半径
的圆里呢? 貌似应该用hash table,hash function怎么选呢? | c********t
发帖数: 5706 | 2 1.先筛选出 以p为中心，边长2r的方形 的所有点
2.将1中的所有点，与p算距离，小于等于r的所有点是结果
复杂度O(n),空间O(1)
没用什么算法，数据结构只用了array，第一遍筛选主要是计算简单
【在 s*******k 的大作中提到】
: 【 以下文字转载自 CS 讨论区 】
: 发信人: stonerock (rock), 信区: CS
: 标 题: 算法问题
: 发信站: BBS 未名空间站 (Sat Jul 2 00:35:17 2011, 美东)
: 平面上有N个点,给你其中一个点p和半径r,怎么最快找到哪些点落在以p为中心r为半径
: 的圆里呢? 貌似应该用hash table,hash function怎么选呢?
| s*******k
发帖数: 227 | 3 1你怎么选? loop all points?
【在 c********t 的大作中提到】
: 1.先筛选出 以p为中心，边长2r的方形 的所有点
: 2.将1中的所有点，与p算距离，小于等于r的所有点是结果
: 复杂度O(n),空间O(1)
: 没用什么算法，数据结构只用了array，第一遍筛选主要是计算简单
| c********t
发帖数: 5706 | 4 是啊，loop，找条件附和 Px-r <= Ix<= Px+r, Py-r <= Iy <= Py+r的点。
【在 s*******k 的大作中提到】
: 1你怎么选? loop all points?
| g*********e
发帖数: 14401 | 5
of course you have traverse all points, the lower bound of O(n),
【在 s*******k 的大作中提到】
: 1你怎么选? loop all points?
|
|
