给定 N 个基础点坐标(x,y)，求离指定点(px,py)最近的基础点
基础点可以预处理
要求时间复杂度<N
基础点可以预处理
要求时间复杂度<N
This topic created in 3353 days ago, the information mentioned may be changed or developed.
 |
aheadleadSep 4, 2017
1
什么叫“基础点”
|
 |
xiang578Sep 4, 2017 via iPhone
2
不知道是不是 kd tree
|
 |
GreatHumoristSep 4, 2017 via iPhone
3
向量计算公式？
|
 |
4
|
1 |
blahgeekSep 4, 2017 via iPhone
6
|
 |
lsmgeb89Sep 4, 2017
7
这种算计算几何领域的算法？
|
 |
yangffSep 4, 2017
9
具体你可以看 voronoi 图的扫描线构造方法，反正你是一次性的。
|
 |
ryd994Sep 4, 2017 via Android
10
这也叫难？你想想手机基站的工作范围就可以想通了
剩下的是怎么把想法转化为算法 |
 |
jedihySep 5, 2017
11
google onsite 题，转换为极座标之后二分搜索
|
|
jedihySep 5, 2017
12
@yangff 预处理不能给你这样预处理的，你这样我直接算距离初始化的时候 O(N)就全部做完了。
原题是说可以你可以选择给出的坐标的形式，然后让你找出距离最近的点。提示也很明显<O(N)，那就是 O(nlogn)了。 |
 |
17
|
 |
linux40Sep 5, 2017 via Android
18
极坐标二分要用到极坐标下的距离公式吧。
|
 |
messyideaSep 5, 2017
19
想来想去总感觉极坐标二分不了(
能想到一些杂七杂八预处理优化的办法, 但都能构造出在极端情况下退化到 O(N)的情况. 坐等正解 |
|
ValyrianSep 5, 2017 via iPad
20
@jlsk 查找是 O(log n)，plane subdivision： http://www.cs.cmu.edu/afs/cs/academic/class/15456-s10/ClassNotes/kirkpatrick.pdf
|
 |
helicaSep 5, 2017 via iPhone
21
量化后，线段树乱搞吧
|
|
yangffSep 5, 2017
23
hmm …… 如果你的 px, py 不是预先给出的话，查询是 logn 的
至于你可以用的各种算法你可以参考一下这本书…… 计算几何--算法与应用(第三版) |
 |
GtDzxSep 5, 2017
24
话说 google onsite 出这题的话是想听到什么回答呢？
我如果说我知道可以用 voronoi 图搞，但是具体怎么搞不会。是不是直接就跪了 -_-!! 要不然是可以先假设基础点分布比较随机，扯一扯 kd-tree/geohash 以及 google s2 库的实现？ |
 |
northislandSep 5, 2017
25
图片搜索 CBIR，或者图片配准中，的最基础问题了。
属于暴力搜索的近似问题， 现在最流行 Optimized Product Quantization 和 Product Quantization Tree。之前的 FLANN （ kd-Trees 和 K-Mean Trees 结合）也很经典。 https://github.com/yahoo/lopq https://github.com/cgtuebingen/Product-Quantization-Tree 那都是高维数据的玩法，这就是二维。 |
 |
1djmaoSep 5, 2017
26
|
 |
rashawnSep 5, 2017 via iPhone
27
预处理是啥意思…
|
 |
zagrebSep 5, 2017 via iPhone
28
前几天不是有人发帖问“已知调色板中 N 个基本颜色，求任意颜色在调色板中最接近的颜色？”么。一个二位空间，一个 rgb 色彩空间。
|
 |
artandlolOct 26, 2017 via Android
29
傻比
|
Select Language