m******t
发帖数: 273 | 1 【 以下文字转载自 Quant 讨论区 】
发信人: myregmit (myregmit), 信区: Quant
标 题: 问一道面试题, 关于算法
发信站: BBS 未名空间站 (Fri Oct 31 21:59:40 2014, 美东)
各位达人
问一道面试题，
在一个二维平面上， 给定一些点， 每个点的坐标已知， 每个点有一个正数来表示它
的价值。
另外， 给定一个 正数 R。
如何 在该平面上 快速找到 一个点， 使得以此点为圆心， R 为半径的圆内， 所有点
的价值总和最大。
要求 算法的 时间 和 空间 效率最优。
谢谢 |
y*********i
发帖数: 19 | 2 我有一个拙见不知道对不对，先算出所有两两点之间的距离，然后像kruskal一样，排
序，从小到大取最小的不超过2R的边，把两个点放到一个cluster里（可能有重复），
最后扫一遍所有cluster看哪个最多。n^2复杂度吧 |
m******t
发帖数: 273 | 3 【 以下文字转载自 Quant 讨论区 】
发信人: myregmit (myregmit), 信区: Quant
标 题: 问一道面试题, 关于算法
发信站: BBS 未名空间站 (Fri Oct 31 21:59:40 2014, 美东)
各位达人
问一道面试题，
在一个二维平面上， 给定一些点， 每个点的坐标已知， 每个点有一个正数来表示它
的价值。
另外， 给定一个 正数 R。
如何 在该平面上 快速找到 一个点， 使得以此点为圆心， R 为半径的圆内， 所有点
的价值总和最大。
要求 算法的 时间 和 空间 效率最优。
谢谢 |
y*********i
发帖数: 19 | 4 我有一个拙见不知道对不对，先算出所有两两点之间的距离，然后像kruskal一样，排
序，从小到大取最小的不超过2R的边，把两个点放到一个cluster里（可能有重复），
最后扫一遍所有cluster看哪个最多。n^2复杂度吧 |
r****7
发帖数: 2282 | 5 kruskal是两两间的距离，从小到大取不超过2R的边又不能保证一个cluster里的所有点
在一个半径是R得圆里
应该是divided & conquer + DP吧
【在 y*********i 的大作中提到】
: 我有一个拙见不知道对不对，先算出所有两两点之间的距离，然后像kruskal一样，排
: 序，从小到大取最小的不超过2R的边，把两个点放到一个cluster里（可能有重复），
: 最后扫一遍所有cluster看哪个最多。n^2复杂度吧
|
l*********8
发帖数: 4642 | 6 我觉着用退火算法
【在 m******t 的大作中提到】
: 【 以下文字转载自 Quant 讨论区 】
: 发信人: myregmit (myregmit), 信区: Quant
: 标 题: 问一道面试题, 关于算法
: 发信站: BBS 未名空间站 (Fri Oct 31 21:59:40 2014, 美东)
: 各位达人
: 问一道面试题，
: 在一个二维平面上， 给定一些点， 每个点的坐标已知， 每个点有一个正数来表示它
: 的价值。
: 另外， 给定一个 正数 R。
: 如何 在该平面上 快速找到 一个点， 使得以此点为圆心， R 为半径的圆内， 所有点
|
a******u
发帖数: 69 | 7 枚举每对距离小于2R的点对p, q
对于每个点对p, q
然后做一个半径为R的圆经过这p, q两点。(PS: 对于每个点对p, q, 有两个满足该条件
的圆)
把平面内所有在此圆的点的价值加起来。
找出最大的一个价值和就是答案。
总时间复杂度O(n^3)
不知道有没有更快的方法。 |
w***w
发帖数: 84 | 8 以每个点为圆心，画半径为R的圆，对每个小块计价，选最大的，时间复杂度 n^2. |
q*c
发帖数: 9453 | 9 圆心为啥一定要在点上？
【在 w***w 的大作中提到】
: 以每个点为圆心，画半径为R的圆，对每个小块计价，选最大的，时间复杂度 n^2.
|
m******t
发帖数: 273 | 10 What is 每个小块 ?
thanks
【在 w***w 的大作中提到】
: 以每个点为圆心，画半径为R的圆，对每个小块计价，选最大的，时间复杂度 n^2.
|
|
|
m******t
发帖数: 273 | 11 The circle center is not required to be on one of the given points.
thanks !
【在 q*c 的大作中提到】
: 圆心为啥一定要在点上？
|
w***w
发帖数: 84 | 12 A 在B为圆心半径为R的圆内当且仅当反之亦然 所以等价问题是以每点为圆心画圆看平
面上哪个点被 cover 最多
这些圆分割平面为 n^2块 在这―时间内也能算 不过有点麻烦 或是把圆切成小方块用
hash 的办法 这样是线性时间 不过是近似解 |
m******t
发帖数: 273 | 13 for "A 在B为圆心半径为R的圆内当且仅当反之亦然 所以等价问题是以每点为圆心画圆
看平
-- it is O(n^2) 因为， 决定 N 个点是否在一个圆内 需要 O（N）， 对于 N个
园 则 需要 O（N^2）。
“这些圆分割平面为 n^2块 在这―时间内也能算”
－－ 怎么计算 呢 ？
“把圆切成小方块用: hash 的办法 这样是线性时间 不过是近似解”
－－ 为什么用 hash 就是线性 ？
thanks !
用 |
w***w
发帖数: 84 | 14 我说的是把问题转为 给你n个圆，each with a value, 平面上哪个点被 cover 的价值
最大。简单点的算法是把两两交点都算出来，沿每个圆排序后形成平面图 再找每个
face. hash 的话就是平面上画grid, 对每个cover的小方块作hash.
如果是面试题，这些提示你还不会的话，这个职位就别试了，去了你也不高兴的。 |
q*c
发帖数: 9453 | 15 这才是让问题变的难以快速解决。
【在 m******t 的大作中提到】
: The circle center is not required to be on one of the given points.
: thanks !
|
y*d
发帖数: 2226 | 16 买买提的水平真让人捉急啊。老夫周五晚上看到这个题，想出了解法，觉着不难，别人
应该能做出来，所以就懒得码字了。结果，两天过去了，居然还没争论清楚 :(
这个题有意思的地方就在于平面上任何一个区域里可以做圆心的点都有Aleph 1个。这
让直接的枚举、DP、搜索、逼近都不好使。
矿工版上有人给出了一个枚举点集的替代方案。这个算法让枚举变得可行，很好！但是
，时间复杂度偏高。这个相当于要枚举输入点集的所有子集。需要O（2^n)的时间。
矿工版上的另一个整数化的方法，确实是抓住了一大类CS问题的命门：你在电脑里很难
真的给出一个无理数出来。所以你确实可以找出一个所有点坐标的“最大公约数”。但
是，如果我非要说第一个点在(0,pi)，第二个点在(e, 0)， ...... 呢？再说，就算是
可以整数化的情况下，这个计算量也可能超大无比。这种做法，终究是失去了原题数学
上的美感。
Job版上autumnhu的算法是对的，但是没有给出解释，而且有一个小错
我来解释一下吧
假设，可以达到的最大价值是M
根据定义，必有一个圆c满足c内的所有点（表示为P(c)）的value的总和等于M
可以证明，一定存在c'满足
1. P(c') = P(c)
2. c'的半径是R
3. 有两个输入点集（p）内的点在c'上（在圆周上，或在圆周内侧无限接近于圆周）
证明的方法是：
1。如果c不满足条件3，则可以平移c，直到有一个P(c)中的点即将移出c。平移得到的c
"满足P(c")=P(c)，并且有一个点在c"上
2。以这个点为轴，转动c"，直到有一个P(c)中的点即将转出。这时就得到我们要的c'
所以，我们只需要枚举所有可能的c'即可。
foreach p1 属于p
foreach p2 属于p且不等于p1
列方程，解出到p1，p2距离都等于R的点
这个2次方程会有0,1,2个解（autumnhu在这里想错了），设解集为X
foreach x 属于 X
做x为圆心，半径为R的圆C(x,R)
计算这个圆内所有点的value的和
输出value和最大的那个x
时间复杂度O(n^3) |
w***w
发帖数: 84 | 17 我12楼上是O(n^2 log n)的解法。智商真的是捉急。 |
n****2
发帖数: 307 | |
e*******s
发帖数: 1979 | 19 哥你太搞笑了 brute force就是O(n^3)....
【在 y*d 的大作中提到】
: 买买提的水平真让人捉急啊。老夫周五晚上看到这个题，想出了解法，觉着不难，别人
: 应该能做出来，所以就懒得码字了。结果，两天过去了，居然还没争论清楚 :(
: 这个题有意思的地方就在于平面上任何一个区域里可以做圆心的点都有Aleph 1个。这
: 让直接的枚举、DP、搜索、逼近都不好使。
: 矿工版上有人给出了一个枚举点集的替代方案。这个算法让枚举变得可行，很好！但是
: ，时间复杂度偏高。这个相当于要枚举输入点集的所有子集。需要O（2^n)的时间。
: 矿工版上的另一个整数化的方法，确实是抓住了一大类CS问题的命门：你在电脑里很难
: 真的给出一个无理数出来。所以你确实可以找出一个所有点坐标的“最大公约数”。但
: 是，如果我非要说第一个点在(0,pi)，第二个点在(e, 0)， ...... 呢？再说，就算是
: 可以整数化的情况下，这个计算量也可能超大无比。这种做法，终究是失去了原题数学
|
