m******t
发帖数: 273 | 1 各位达人
问一道面试题，
在一个二维平面上， 给定一些点， 每个点的坐标已知， 每个点有一个正数来表示它
的价值。
另外， 给定一个 正数 R。
如何 在该平面上 快速找到 一个点， 使得以此点为圆心， R 为半径的圆内， 所有点
的价值总和最大。
要求 算法的 时间 和 空间 效率最优。
谢谢 |
l*********g
发帖数: 1899 | 2 假设这个二维平面上有n个任意分布的点（n是任意正整数），并标记为d1......dn。先
把n个点中任意两点间的距离都算一次，然后把凡是任意两点间的距离小于等于2R的视
为在同一个圆中。例如，如算得d1，d2，d3中任意两点间距离小于等于2R（即d1和d2，
d1和d3，d2和d3，之间的距离各小于等于2R），则视d1，d2，d3在一个圆内，再计算圆
中各点d1，d2，d3的价值总和，称此总和为y1。如用同理，又算得d1，d4，d5，d6，d7
中任意两点间距离小于等于2R，则视d1，d4，d5，d6，d7在同一个圆内，并计算得到圆
中各点d1，d4，d5，d6，d7价值总和为y2。如用同理再可得到y3，…，yn，然后比较得
出y1，y2，y3，……，yn中的最大值就可以确定这个要找的圆，再根据圆内的点的坐标
值和R可算得圆心坐标。这个圆心坐标可以不是唯一值（例如圆心的偏移不影响这个圆
能包含这些点的时候）。
如有某（些）点和其他点之间的距离都大于2R，则该点可单独待在一个圆内，然后把该
点的价值和y1，y2，y3，……，yn中的最大值进行比较，如为最大同理求圆心坐标。
以上是理论思路。如果实际应用中，有具体的点数；点数不多；点的价值相差悬殊；又
或者点之间很聚集、距离短；又或者有其他明显可观察到的规律，就不需要用以上思路
，而是根据实际情况用一些针对性强的方法会更快。
【在 m******t 的大作中提到】
: 各位达人
: 问一道面试题，
: 在一个二维平面上， 给定一些点， 每个点的坐标已知， 每个点有一个正数来表示它
: 的价值。
: 另外， 给定一个 正数 R。
: 如何 在该平面上 快速找到 一个点， 使得以此点为圆心， R 为半径的圆内， 所有点
: 的价值总和最大。
: 要求 算法的 时间 和 空间 效率最优。
: 谢谢
|
m******t
发帖数: 273 | 3 Thanks ! It works.
but, the time and space complexity is O(n^2).
If n is large, e.g. 3,000,000, it still takes a long time.
Are there better algorithms that can improve it to O(n lg(n)) ?
Any help would be appreciated.
Thanks !
d7
【在 l*********g 的大作中提到】
: 假设这个二维平面上有n个任意分布的点（n是任意正整数），并标记为d1......dn。先
: 把n个点中任意两点间的距离都算一次，然后把凡是任意两点间的距离小于等于2R的视
: 为在同一个圆中。例如，如算得d1，d2，d3中任意两点间距离小于等于2R（即d1和d2，
: d1和d3，d2和d3，之间的距离各小于等于2R），则视d1，d2，d3在一个圆内，再计算圆
: 中各点d1，d2，d3的价值总和，称此总和为y1。如用同理，又算得d1，d4，d5，d6，d7
: 中任意两点间距离小于等于2R，则视d1，d4，d5，d6，d7在同一个圆内，并计算得到圆
: 中各点d1，d4，d5，d6，d7价值总和为y2。如用同理再可得到y3，…，yn，然后比较得
: 出y1，y2，y3，……，yn中的最大值就可以确定这个要找的圆，再根据圆内的点的坐标
: 值和R可算得圆心坐标。这个圆心坐标可以不是唯一值（例如圆心的偏移不影响这个圆
: 能包含这些点的时候）。
|
m******t
发帖数: 273 | 4 各位达人
问一道面试题，
在一个二维平面上， 给定一些点， 每个点的坐标已知， 每个点有一个正数来表示它
的价值。
另外， 给定一个 正数 R。
如何 在该平面上 快速找到 一个点， 使得以此点为圆心， R 为半径的圆内， 所有点
的价值总和最大。
要求 算法的 时间 和 空间 效率最优。
谢谢 |
l*********g
发帖数: 1899 | 5 假设这个二维平面上有n个任意分布的点（n是任意正整数），并标记为d1......dn。先
把n个点中任意两点间的距离都算一次，然后把凡是任意两点间的距离小于等于2R的视
为在同一个圆中。例如，如算得d1，d2，d3中任意两点间距离小于等于2R（即d1和d2，
d1和d3，d2和d3，之间的距离各小于等于2R），则视d1，d2，d3在一个圆内，再计算圆
中各点d1，d2，d3的价值总和，称此总和为y1。如用同理，又算得d1，d4，d5，d6，d7
中任意两点间距离小于等于2R，则视d1，d4，d5，d6，d7在同一个圆内，并计算得到圆
中各点d1，d4，d5，d6，d7价值总和为y2。如用同理再可得到y3，…，yn，然后比较得
出y1，y2，y3，……，yn中的最大值就可以确定这个要找的圆，再根据圆内的点的坐标
值和R可算得圆心坐标。这个圆心坐标可以不是唯一值（例如圆心的偏移不影响这个圆
能包含这些点的时候）。
如有某（些）点和其他点之间的距离都大于2R，则该点可单独待在一个圆内，然后把该
点的价值和y1，y2，y3，……，yn中的最大值进行比较，如为最大同理求圆心坐标。
以上是理论思路。如果实际应用中，有具体的点数；点数不多；点的价值相差悬殊；又
或者点之间很聚集、距离短；又或者有其他明显可观察到的规律，就不需要用以上思路
，而是根据实际情况用一些针对性强的方法会更快。
【在 m******t 的大作中提到】
: 各位达人
: 问一道面试题，
: 在一个二维平面上， 给定一些点， 每个点的坐标已知， 每个点有一个正数来表示它
: 的价值。
: 另外， 给定一个 正数 R。
: 如何 在该平面上 快速找到 一个点， 使得以此点为圆心， R 为半径的圆内， 所有点
: 的价值总和最大。
: 要求 算法的 时间 和 空间 效率最优。
: 谢谢
|
m******t
发帖数: 273 | 6 Thanks ! It works.
but, the time and space complexity is O(n^2).
If n is large, e.g. 3,000,000, it still takes a long time.
Are there better algorithms that can improve it to O(n lg(n)) ?
Any help would be appreciated.
Thanks !
d7
【在 l*********g 的大作中提到】
: 假设这个二维平面上有n个任意分布的点（n是任意正整数），并标记为d1......dn。先
: 把n个点中任意两点间的距离都算一次，然后把凡是任意两点间的距离小于等于2R的视
: 为在同一个圆中。例如，如算得d1，d2，d3中任意两点间距离小于等于2R（即d1和d2，
: d1和d3，d2和d3，之间的距离各小于等于2R），则视d1，d2，d3在一个圆内，再计算圆
: 中各点d1，d2，d3的价值总和，称此总和为y1。如用同理，又算得d1，d4，d5，d6，d7
: 中任意两点间距离小于等于2R，则视d1，d4，d5，d6，d7在同一个圆内，并计算得到圆
: 中各点d1，d4，d5，d6，d7价值总和为y2。如用同理再可得到y3，…，yn，然后比较得
: 出y1，y2，y3，……，yn中的最大值就可以确定这个要找的圆，再根据圆内的点的坐标
: 值和R可算得圆心坐标。这个圆心坐标可以不是唯一值（例如圆心的偏移不影响这个圆
: 能包含这些点的时候）。
|
a******u
发帖数: 69 | 7 "例如，如算得d1，d2，d3中任意两点间距离小于等于2R（即d1和d2，
d1和d3，d2和d3，之间的距离各小于等于2R），则视d1，d2，d3在一个圆内"
菜鸟弱弱的问一句，求大牛指教。如果d1, d2, d3刚好在等边三角形上。d1，d2，d3就
不能在同一个圆上了吧？？Do I miss something?
d7
【在 l*********g 的大作中提到】
: 假设这个二维平面上有n个任意分布的点（n是任意正整数），并标记为d1......dn。先
: 把n个点中任意两点间的距离都算一次，然后把凡是任意两点间的距离小于等于2R的视
: 为在同一个圆中。例如，如算得d1，d2，d3中任意两点间距离小于等于2R（即d1和d2，
: d1和d3，d2和d3，之间的距离各小于等于2R），则视d1，d2，d3在一个圆内，再计算圆
: 中各点d1，d2，d3的价值总和，称此总和为y1。如用同理，又算得d1，d4，d5，d6，d7
: 中任意两点间距离小于等于2R，则视d1，d4，d5，d6，d7在同一个圆内，并计算得到圆
: 中各点d1，d4，d5，d6，d7价值总和为y2。如用同理再可得到y3，…，yn，然后比较得
: 出y1，y2，y3，……，yn中的最大值就可以确定这个要找的圆，再根据圆内的点的坐标
: 值和R可算得圆心坐标。这个圆心坐标可以不是唯一值（例如圆心的偏移不影响这个圆
: 能包含这些点的时候）。
|
g******g
发帖数: 289 | 8 我觉得这比较像Image Process的算法题了。假设所有的坐标都是整数, 是不是可以这
样做？
1. 确认x和y方向上搜索的范围。按照搜索范围初始一块memory，每个点上的初始值都
为0。
2. 访问每一个给定点，然后把这个点附近的和它距离小于R的点都加上这个点的正数值
，同时记录下有最大值点的坐标。
计算时间应该是O(n)。 |
n******t
发帖数: 4406 | 9 同学，你以后可能很有前途。
【在 g******g 的大作中提到】
: 我觉得这比较像Image Process的算法题了。假设所有的坐标都是整数, 是不是可以这
: 样做？
: 1. 确认x和y方向上搜索的范围。按照搜索范围初始一块memory，每个点上的初始值都
: 为0。
: 2. 访问每一个给定点，然后把这个点附近的和它距离小于R的点都加上这个点的正数值
: ，同时记录下有最大值点的坐标。
: 计算时间应该是O(n)。
|
n******t
发帖数: 4406 | 10 说实话，都到现在这个时候了，这些公司还在考这些和以后工作完全无关的题，不觉得
自己很无聊吗？？？？
【在 m******t 的大作中提到】
: 各位达人
: 问一道面试题，
: 在一个二维平面上， 给定一些点， 每个点的坐标已知， 每个点有一个正数来表示它
: 的价值。
: 另外， 给定一个 正数 R。
: 如何 在该平面上 快速找到 一个点， 使得以此点为圆心， R 为半径的圆内， 所有点
: 的价值总和最大。
: 要求 算法的 时间 和 空间 效率最优。
: 谢谢
|
|
|
m******t
发帖数: 273 | 11 谢谢
每个点的坐标不一定是整数。
请问， 即使 是的话， 如何在 X， Y 方向上搜索 ？
在 X 方向上 接近， 不一定在 Y方向上 也接近。
而且每一个点都要和其他点 比较，
时间还是 O(n^2)
谢谢
【在 g******g 的大作中提到】
: 我觉得这比较像Image Process的算法题了。假设所有的坐标都是整数, 是不是可以这
: 样做？
: 1. 确认x和y方向上搜索的范围。按照搜索范围初始一块memory，每个点上的初始值都
: 为0。
: 2. 访问每一个给定点，然后把这个点附近的和它距离小于R的点都加上这个点的正数值
: ，同时记录下有最大值点的坐标。
: 计算时间应该是O(n)。
|
g******g
发帖数: 289 | 12 如果不是整数，是不是可以整数化？比如我们可以定义一个比较小的unit，然后把所有
坐标整数化。
我说的是x和y方向上的搜索范围，在所有给定点中，用最小的x减R，最大的x加R，用最
小的y减R，最大的y加R。这就是我们要考虑的范围。
如果有n个点，只需要在每个点附近2R*2R的范围内做加法运算就可以了。如果n远远大
于R，运算时间就是O（n).
【在 m******t 的大作中提到】
: 谢谢
: 每个点的坐标不一定是整数。
: 请问， 即使 是的话， 如何在 X， Y 方向上搜索 ？
: 在 X 方向上 接近， 不一定在 Y方向上 也接近。
: 而且每一个点都要和其他点 比较，
: 时间还是 O(n^2)
: 谢谢
|
g*****o
发帖数: 812 | 13 你这个方法不就是每个点穷举么...
【在 g******g 的大作中提到】
: 如果不是整数，是不是可以整数化？比如我们可以定义一个比较小的unit，然后把所有
: 坐标整数化。
: 我说的是x和y方向上的搜索范围，在所有给定点中，用最小的x减R，最大的x加R，用最
: 小的y减R，最大的y加R。这就是我们要考虑的范围。
: 如果有n个点，只需要在每个点附近2R*2R的范围内做加法运算就可以了。如果n远远大
: 于R，运算时间就是O（n).
|
m******t
发帖数: 273 | 14 找到最大， 最小的 X， Y 需要 O（n lg n）。
为什麽 要整数化 ？ R 不一定是整数 。
而且， 如果不比较每一个点， 如何知道， 每个点是否在2R * 2R 范围内 ？
So, it is still O(n^2) ?
谢谢
【在 g******g 的大作中提到】
: 如果不是整数，是不是可以整数化？比如我们可以定义一个比较小的unit，然后把所有
: 坐标整数化。
: 我说的是x和y方向上的搜索范围，在所有给定点中，用最小的x减R，最大的x加R，用最
: 小的y减R，最大的y加R。这就是我们要考虑的范围。
: 如果有n个点，只需要在每个点附近2R*2R的范围内做加法运算就可以了。如果n远远大
: 于R，运算时间就是O（n).
|
g******g
发帖数: 289 | 15 找最大和最小的值，只需要O(n), 因为不是排序。
如果是非整数值，就可能存在无穷多解，整数化可以简化问题，比如，我们可以用R/10
作为unit。
你有n个点，你知道每个点的坐标(xi,yi), 只需要处理在范围 (xi-R, xi+R)和范围(yi
-R, yi+R)中已经被整数化的点就可以了，当然，这个点到(xi,yi)的距离必须小于R。
当R远小于n的时候，在每个给定位置满足条件的点的数目也会远小于n。所以，计算时
间还是O(n)。
【在 m******t 的大作中提到】
: 找到最大， 最小的 X， Y 需要 O（n lg n）。
: 为什麽 要整数化 ？ R 不一定是整数 。
: 而且， 如果不比较每一个点， 如何知道， 每个点是否在2R * 2R 范围内 ？
: So, it is still O(n^2) ?
: 谢谢
|
m******t
发帖数: 273 | 16 对于 点 (xi,yi) 来说， 如何确定 其他 N－1 个点 是否在范围 (xi-R, xi+R)和
范围(yi-R, yi+R) 中 ？ 如果 不穷举每一个点， 会不会漏掉 ？
thanks !
10
yi
【在 g******g 的大作中提到】
: 找最大和最小的值，只需要O(n), 因为不是排序。
: 如果是非整数值，就可能存在无穷多解，整数化可以简化问题，比如，我们可以用R/10
: 作为unit。
: 你有n个点，你知道每个点的坐标(xi,yi), 只需要处理在范围 (xi-R, xi+R)和范围(yi
: -R, yi+R)中已经被整数化的点就可以了，当然，这个点到(xi,yi)的距离必须小于R。
: 当R远小于n的时候，在每个给定位置满足条件的点的数目也会远小于n。所以，计算时
: 间还是O(n)。
|
g******g
发帖数: 289 | 17 举一个例子，比如说，有两个点(10.5,10.1)和(20.1,20.1), 他们对应的正数分别是3
和7，R是10。那我们用1作为unit，在第一个点附近，取值范围是[0.5, 20.5]和[0.1,
20.1], 我们需要枚举从(1, 1) 到（20，20）共有400个点，这些点里如果距离(10.5,
10.1)小于10，就把那里的值加上给定正数3。对第二个点也做同样处理，枚举从(11,
11) 到（30，30）共有400个点，这些点里如果距离(20.1,20.1)小于10，就把那里的值
加上给定正数7。最后，再检查从(1, 1) 到（30，30）这些点上的坐标值，找出最大数
10对应的那个点，比如说(15, 15)。
如果比较N个点中任意两个点的距离，当N比较大的时候，就很慢了。我是不主张这么做
。你觉得呢？
范围(yi-R, yi+R) 中 ？ 如果 不穷举每一个点， 会不会漏掉 ？
【在 m******t 的大作中提到】
: 对于 点 (xi,yi) 来说， 如何确定 其他 N－1 个点 是否在范围 (xi-R, xi+R)和
: 范围(yi-R, yi+R) 中 ？ 如果 不穷举每一个点， 会不会漏掉 ？
: thanks !
:
: 10
: yi
|
r***r
发帖数: 153 | 18 感觉O(n^2)不可避免，举个特例，如果任何一对点距离都小于R，那么每个点的最终
score都要加上其他所有点的值。当然这个例子比较诡异，因为所有点的最终score都一
样。那么我们还可以建立一个特例，使得每个点的R-ball都包括所有的点except for
one other dot。那么所有点的最终score就不一样了。
也许可以搞个output-sensitive的算法，使得最终结果depends on K, K是所有R-ball
的包含的最多的点的数目。
【在 m******t 的大作中提到】
: 各位达人
: 问一道面试题，
: 在一个二维平面上， 给定一些点， 每个点的坐标已知， 每个点有一个正数来表示它
: 的价值。
: 另外， 给定一个 正数 R。
: 如何 在该平面上 快速找到 一个点， 使得以此点为圆心， R 为半径的圆内， 所有点
: 的价值总和最大。
: 要求 算法的 时间 和 空间 效率最优。
: 谢谢
|
g*****o
发帖数: 812 | 19 呃，电脑不是人眼，看一眼就能看出二维平面范围。查找的话就要o（log n）吧
3
,
【在 g******g 的大作中提到】
: 举一个例子，比如说，有两个点(10.5,10.1)和(20.1,20.1), 他们对应的正数分别是3
: 和7，R是10。那我们用1作为unit，在第一个点附近，取值范围是[0.5, 20.5]和[0.1,
: 20.1], 我们需要枚举从(1, 1) 到（20，20）共有400个点，这些点里如果距离(10.5,
: 10.1)小于10，就把那里的值加上给定正数3。对第二个点也做同样处理，枚举从(11,
: 11) 到（30，30）共有400个点，这些点里如果距离(20.1,20.1)小于10，就把那里的值
: 加上给定正数7。最后，再检查从(1, 1) 到（30，30）这些点上的坐标值，找出最大数
: 10对应的那个点，比如说(15, 15)。
: 如果比较N个点中任意两个点的距离，当N比较大的时候，就很慢了。我是不主张这么做
: 。你觉得呢？
:
|
j******n
发帖数: 91 | 20 我觉得你说得很对啊。如果这样的话，前一位大牛的方法也许就不成立了。应该怎么修
改呢？算了，我也不求什么O(n)的方法，我只想知道正常思路怎么解决。
【在 a******u 的大作中提到】
: "例如，如算得d1，d2，d3中任意两点间距离小于等于2R（即d1和d2，
: d1和d3，d2和d3，之间的距离各小于等于2R），则视d1，d2，d3在一个圆内"
: 菜鸟弱弱的问一句，求大牛指教。如果d1, d2, d3刚好在等边三角形上。d1，d2，d3就
: 不能在同一个圆上了吧？？Do I miss something?
:
: d7
|
|
|
l*********g
发帖数: 1899 | 21 我其实不明白你不明白什么。呵呵。
首先，你问“如果d1, d2, d3刚好在等边三角形上。d1，d2，d3就不能在同一个圆上了
吧？”。这点我个人认为非常显而易见的，就是未必。你看一眼我附的图，很明显，如
果d1，d2，d3分别在等边三角形的3个顶点上，他们就在同一个圆上了吧。因为我觉得
这个问题很显然，以至我怀疑我是否已经明白你不明白什么。
另外，不管d1, d2, d3分别在这个等边三角形的边上也好，顶点也好，只要这3个点符
合“任意两点间距离小于等于2R”，则可视为在同一个直径为2R的圆内（在圆边上时，
我也将其纳入属于圆内的范围，就像打羽毛球，球踏界属于“good ball”。）这点，
在我附的图中也很容易看出来，就是d1, d2, d3不管在等边三角形的边好，顶点好，他
们都是在圆内（边）的。
我认为我的思路如果写成算法，关键是如何写好一个查找算法不要漏掉每个组（属于同
一个圆）中的任何一个点，其实就是要把每一组中符合“任意两点间距离小于等于2R”
的所有点要找齐全，不能漏掉其中任何一个。d1, d2, d3只是我举个例子说明思路，还
是比较简单的。实际应用中，每组的点数有可能是个庞大的正整数。
【在 a******u 的大作中提到】
: "例如，如算得d1，d2，d3中任意两点间距离小于等于2R（即d1和d2，
: d1和d3，d2和d3，之间的距离各小于等于2R），则视d1，d2，d3在一个圆内"
: 菜鸟弱弱的问一句，求大牛指教。如果d1, d2, d3刚好在等边三角形上。d1，d2，d3就
: 不能在同一个圆上了吧？？Do I miss something?
:
: d7
|
y*d
发帖数: 2226 | 22 买买提的水平真让人捉急啊。老夫周五晚上看到这个题，想出了解法，觉着不难，别人
应该能做出来，所以就懒得码字了。结果，两天过去了，居然还没争论清楚 :(
这个题有意思的地方就在于平面上任何一个区域里可以做圆心的点都有Aleph 1个。这
让直接的枚举、DP、搜索、逼近都不好使。
矿工版上有人给出了一个枚举点集的替代方案。这个算法让枚举变得可行，很好！但是
，时间复杂度偏高。这个相当于要枚举输入点集的所有子集。需要O（2^n)的时间。很
难理解矿工版里几个人都把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) |
y*d
发帖数: 2226 | 23 autumnhu同学的初中数学底子还是欠一点
两边之和大于第三边
二次方程的解集有0，1，2三种可能
这些都是初中学的
【在 l*********g 的大作中提到】
: 我其实不明白你不明白什么。呵呵。
: 首先，你问“如果d1, d2, d3刚好在等边三角形上。d1，d2，d3就不能在同一个圆上了
: 吧？”。这点我个人认为非常显而易见的，就是未必。你看一眼我附的图，很明显，如
: 果d1，d2，d3分别在等边三角形的3个顶点上，他们就在同一个圆上了吧。因为我觉得
: 这个问题很显然，以至我怀疑我是否已经明白你不明白什么。
: 另外，不管d1, d2, d3分别在这个等边三角形的边上也好，顶点也好，只要这3个点符
: 合“任意两点间距离小于等于2R”，则可视为在同一个直径为2R的圆内（在圆边上时，
: 我也将其纳入属于圆内的范围，就像打羽毛球，球踏界属于“good ball”。）这点，
: 在我附的图中也很容易看出来，就是d1, d2, d3不管在等边三角形的边好，顶点好，他
: 们都是在圆内（边）的。
|
g******g
发帖数: 289 | 24 稍稍纠正一下，整数化方法最大问题是可能对内存的需要很大，比如这些点在平面上分
布很广，或者unit很小，但是速度不是问题，O(n)。当然，数学上面也没有什么美感。
【在 y*d 的大作中提到】
: 买买提的水平真让人捉急啊。老夫周五晚上看到这个题，想出了解法，觉着不难，别人
: 应该能做出来，所以就懒得码字了。结果，两天过去了，居然还没争论清楚 :(
: 这个题有意思的地方就在于平面上任何一个区域里可以做圆心的点都有Aleph 1个。这
: 让直接的枚举、DP、搜索、逼近都不好使。
: 矿工版上有人给出了一个枚举点集的替代方案。这个算法让枚举变得可行，很好！但是
: ，时间复杂度偏高。这个相当于要枚举输入点集的所有子集。需要O（2^n)的时间。很
: 难理解矿工版里几个人都把2和n的次序搞反了 :(
: 矿工版上的另一个整数化的方法，确实是抓住了一大类CS问题的命门：你在电脑里很难
: 真的给出一个无理数出来。所以你确实可以找出一个所有点坐标的“最大公约数”。但
: 是，如果我非要说第一个点在(0,pi)，第二个点在(e, 0)， ...... 呢？再说，就算是
|
n******t
发帖数: 4406 | 25 我说过了，你会红的。
【在 g******g 的大作中提到】
: 稍稍纠正一下，整数化方法最大问题是可能对内存的需要很大，比如这些点在平面上分
: 布很广，或者unit很小，但是速度不是问题，O(n)。当然，数学上面也没有什么美感。
|
l*****0
发帖数: 238 | 26 清华大学《信息学奥林匹克竞赛》系列中有一道卫星覆盖范围的题根这个题是一回事。
这道题处理上稍微麻烦一点，但思路是一样的。
把所有的点都当作一个半径为R的圆来处理，系统维护一个链表，记录所有图形以及图
形的权值。比如取来第一个点A后，链表拥有一个节点N1，权值P1。
当取来第二个点B时，如果A与B不相交则简单，把B加入链表即可
算法的核心在于处理B与A相交的情形。
如果B与A相交，则令b=A&B，沿b的轮廓将A，B分割为 A-b，B-b，b三个图形，链表被重
新整理为
(A-b)(B-b)(b) 三个互不相交的元素，每个元素拥有一个确定的权值。将链表重新表示
为N1，N2，N3
当取来第三个点C时，先分析N1与C的相交关系，如果存在相交，则按照同样的方法进行
切割成N1-c,C-c,c=N1&C三个互不相交的图形，每个图形都有新的权值。注意到 (N1-c)
和 (c) 本来是属于N1的，他们和链表中的其他元素（N2，N3）都不相交，可以直接放
回到列表里，剩下图形标记为C'=(C-c)。接下来用同样的方法分析C'和N2的关系，依次
类推，直到剩下和谁都不相交的c''''放到链表里。
第四个点用同样的方法处理。
经过这样一番处理，我们最终得到一个链表，链表里的所有图形都是互不相交的，每个
节点都有一个确定的权值。权值最大的节点就是我们要找的点，该图形的点集就是解集
这个算法的效率是最优的，几乎是线性的。前面提到的n^3算法是正确的，但是效率很
低。
【在 y*d 的大作中提到】
: 买买提的水平真让人捉急啊。老夫周五晚上看到这个题，想出了解法，觉着不难，别人
: 应该能做出来，所以就懒得码字了。结果，两天过去了，居然还没争论清楚 :(
: 这个题有意思的地方就在于平面上任何一个区域里可以做圆心的点都有Aleph 1个。这
: 让直接的枚举、DP、搜索、逼近都不好使。
: 矿工版上有人给出了一个枚举点集的替代方案。这个算法让枚举变得可行，很好！但是
: ，时间复杂度偏高。这个相当于要枚举输入点集的所有子集。需要O（2^n)的时间。很
: 难理解矿工版里几个人都把2和n的次序搞反了 :(
: 矿工版上的另一个整数化的方法，确实是抓住了一大类CS问题的命门：你在电脑里很难
: 真的给出一个无理数出来。所以你确实可以找出一个所有点坐标的“最大公约数”。但
: 是，如果我非要说第一个点在(0,pi)，第二个点在(e, 0)， ...... 呢？再说，就算是
|
y*d
发帖数: 2226 | 27 看不太懂啊
能不能给个例子说明一下？
特别是所谓的权值是怎么算的？
【在 l*****0 的大作中提到】
: 清华大学《信息学奥林匹克竞赛》系列中有一道卫星覆盖范围的题根这个题是一回事。
: 这道题处理上稍微麻烦一点，但思路是一样的。
: 把所有的点都当作一个半径为R的圆来处理，系统维护一个链表，记录所有图形以及图
: 形的权值。比如取来第一个点A后，链表拥有一个节点N1，权值P1。
: 当取来第二个点B时，如果A与B不相交则简单，把B加入链表即可
: 算法的核心在于处理B与A相交的情形。
: 如果B与A相交，则令b=A&B，沿b的轮廓将A，B分割为 A-b，B-b，b三个图形，链表被重
: 新整理为
: (A-b)(B-b)(b) 三个互不相交的元素，每个元素拥有一个确定的权值。将链表重新表示
: 为N1，N2，N3
|
g******g
发帖数: 289 | 28 原理是对的，逻辑不难理解，但是圆形边界的分段处理会非常麻烦。
【在 l*****0 的大作中提到】
: 清华大学《信息学奥林匹克竞赛》系列中有一道卫星覆盖范围的题根这个题是一回事。
: 这道题处理上稍微麻烦一点，但思路是一样的。
: 把所有的点都当作一个半径为R的圆来处理，系统维护一个链表，记录所有图形以及图
: 形的权值。比如取来第一个点A后，链表拥有一个节点N1，权值P1。
: 当取来第二个点B时，如果A与B不相交则简单，把B加入链表即可
: 算法的核心在于处理B与A相交的情形。
: 如果B与A相交，则令b=A&B，沿b的轮廓将A，B分割为 A-b，B-b，b三个图形，链表被重
: 新整理为
: (A-b)(B-b)(b) 三个互不相交的元素，每个元素拥有一个确定的权值。将链表重新表示
: 为N1，N2，N3
|
l*********g
发帖数: 1899 | 29 我也感觉到好像有点Whole Egg Zhang的味道。
【在 n******t 的大作中提到】
: 我说过了，你会红的。
|
s**********1
发帖数: 12 | 30 可不可以对每个点按照横坐标，纵坐标排序
然后，对每个点，按照garyfong的方法计算符合
条件的矩形框内的点的权值和？ |
|
|
l*****0
发帖数: 238 | 31 原题的切割是立方体，非常简洁。这个题是圆，确实比较麻烦，所以可以结合图像处理
的办法，用位图而不是矢量图来描述图形
【在 g******g 的大作中提到】
: 原理是对的，逻辑不难理解，但是圆形边界的分段处理会非常麻烦。
|
l*****0
发帖数: 238 | 32 很简单，圆A的权值是P1，圆B的权值是P2，这是已知条件，那么b=A&B的权值就是P1+P2
,因为以b圆中任一点为圆心做半径为R的圆，都会把A，B点包含进来，所以b圆的价值就
是P1+P2
【在 y*d 的大作中提到】
: 看不太懂啊
: 能不能给个例子说明一下？
: 特别是所谓的权值是怎么算的？
|
j******n
发帖数: 91 | 33 我日，我觉得自己的智商很捉急。看你的附图，假设该等边三角形的边长为2R，你图中
的那个圆的直径是多少？
【在 l*********g 的大作中提到】
: 我其实不明白你不明白什么。呵呵。
: 首先，你问“如果d1, d2, d3刚好在等边三角形上。d1，d2，d3就不能在同一个圆上了
: 吧？”。这点我个人认为非常显而易见的，就是未必。你看一眼我附的图，很明显，如
: 果d1，d2，d3分别在等边三角形的3个顶点上，他们就在同一个圆上了吧。因为我觉得
: 这个问题很显然，以至我怀疑我是否已经明白你不明白什么。
: 另外，不管d1, d2, d3分别在这个等边三角形的边上也好，顶点也好，只要这3个点符
: 合“任意两点间距离小于等于2R”，则可视为在同一个直径为2R的圆内（在圆边上时，
: 我也将其纳入属于圆内的范围，就像打羽毛球，球踏界属于“good ball”。）这点，
: 在我附的图中也很容易看出来，就是d1, d2, d3不管在等边三角形的边好，顶点好，他
: 们都是在圆内（边）的。
|
j******n
发帖数: 91 | 34 我觉得该圆的半径>R了吧？这样不就不符合要求了？卧槽，我的智商真是不行了。
【在 j******n 的大作中提到】
: 我日，我觉得自己的智商很捉急。看你的附图，假设该等边三角形的边长为2R，你图中
: 的那个圆的直径是多少？
|
n******t
发帖数: 4406 | 35 那是神马？
主要是这哥们说话中透露粗的自信，实在是太强大了。
【在 l*********g 的大作中提到】
: 我也感觉到好像有点Whole Egg Zhang的味道。
|
n******t
发帖数: 4406 | 36 这个解法是对的。。。
【在 y*d 的大作中提到】
: 买买提的水平真让人捉急啊。老夫周五晚上看到这个题，想出了解法，觉着不难，别人
: 应该能做出来，所以就懒得码字了。结果，两天过去了，居然还没争论清楚 :(
: 这个题有意思的地方就在于平面上任何一个区域里可以做圆心的点都有Aleph 1个。这
: 让直接的枚举、DP、搜索、逼近都不好使。
: 矿工版上有人给出了一个枚举点集的替代方案。这个算法让枚举变得可行，很好！但是
: ，时间复杂度偏高。这个相当于要枚举输入点集的所有子集。需要O（2^n)的时间。很
: 难理解矿工版里几个人都把2和n的次序搞反了 :(
: 矿工版上的另一个整数化的方法，确实是抓住了一大类CS问题的命门：你在电脑里很难
: 真的给出一个无理数出来。所以你确实可以找出一个所有点坐标的“最大公约数”。但
: 是，如果我非要说第一个点在(0,pi)，第二个点在(e, 0)， ...... 呢？再说，就算是
|
X****r
发帖数: 3557 | 37 到后来单个图形的复杂度本身就是O(n)了啊
【在 l*****0 的大作中提到】
: 原题的切割是立方体，非常简洁。这个题是圆，确实比较麻烦，所以可以结合图像处理
: 的办法，用位图而不是矢量图来描述图形
|
a******7
发帖数: 7 | 38 这都是些什么奇奇怪怪的解法。。。
枚举法怎么可能是O(2^n)呢？ 遍历点列表，和其余每个点算距离，在R内就把值加上。
然后用一个值记录最大价值。 O(n^2)不就解决了？
那个卫星的解法也没好啊，最极端的情况下
2个点 - 〉列表长3
3个点 - 〉列表长7
n个点 - 〉列表长2^n - 1.
这复杂度还没枚举法好啊 |
l*********g
发帖数: 1899 | 39 张全蛋。现在红得不得了那个。
【在 n******t 的大作中提到】
: 那是神马？
: 主要是这哥们说话中透露粗的自信，实在是太强大了。
|
l*********g
发帖数: 1899 | 40 很简单。你暂时不要去想那个等边三角形的事情。
你画个圆，然后你在圆内（包括圆周上）的范围中随意找两个点，你观察一下它们之间
的距离的长度和直径的长度之间的关系。你就会明白了。
【在 j******n 的大作中提到】
: 我觉得该圆的半径>R了吧？这样不就不符合要求了？卧槽，我的智商真是不行了。
|
|
|
T**n
发帖数: 47 | 41 编程菜鸟，ds准备转马工。可不可以从cluster的角度想这个问题？先进行聚类分析，
找出所有两点间距离小于2R的cluster，然后给每个cluster赋上每点的值，找出值最大
的那个cluster，然后我们可以假设最大值得圆一定来自这个cluster，这样我们就缩小
了比较范围，但是这样就算不出复杂度了。 |
g*****o
发帖数: 812 | 42 有这样的聚类方法么. 而且聚类收敛的时间复杂度更高吧
【在 T**n 的大作中提到】
: 编程菜鸟，ds准备转马工。可不可以从cluster的角度想这个问题？先进行聚类分析，
: 找出所有两点间距离小于2R的cluster，然后给每个cluster赋上每点的值，找出值最大
: 的那个cluster，然后我们可以假设最大值得圆一定来自这个cluster，这样我们就缩小
: 了比较范围，但是这样就算不出复杂度了。
|
g******g
发帖数: 289 | 43 一群点在一个圆内可以得出它们间任意两点距离一定小于直径.
一群点如果任意两点距离小于给定直径无法得出它们在一个给定直径的圆内.就如你的
附图一样.
这么多人指出这个问题你还不承认.
你数学怎么学的？
很多时侯也许找不到一种完美算法,但是也别拿一个错误的忽悠人.
全蛋这个名字还是留给你吧,很贴切.
【在 l*********g 的大作中提到】
: 很简单。你暂时不要去想那个等边三角形的事情。
: 你画个圆，然后你在圆内（包括圆周上）的范围中随意找两个点，你观察一下它们之间
: 的距离的长度和直径的长度之间的关系。你就会明白了。
|
l*********g
发帖数: 1899 | 44 请举个反例。
请举出一群点，它们之间任意两点间距离小于等于直径2R的，而它们不能聚在一个直径
为2R的圆内或圆周上的。请举。
像你这种逻辑不清的，我根本没有兴趣和你搭话。如果不是我的朋友问起是神马，我根
本不会理你。
【在 g******g 的大作中提到】
: 一群点在一个圆内可以得出它们间任意两点距离一定小于直径.
: 一群点如果任意两点距离小于给定直径无法得出它们在一个给定直径的圆内.就如你的
: 附图一样.
: 这么多人指出这个问题你还不承认.
: 你数学怎么学的？
: 很多时侯也许找不到一种完美算法,但是也别拿一个错误的忽悠人.
: 全蛋这个名字还是留给你吧,很贴切.
|
n******t
发帖数: 4406 | 45 你的想法真的很正常。。。
【在 a******7 的大作中提到】
: 这都是些什么奇奇怪怪的解法。。。
: 枚举法怎么可能是O(2^n)呢？ 遍历点列表，和其余每个点算距离，在R内就把值加上。
: 然后用一个值记录最大价值。 O(n^2)不就解决了？
: 那个卫星的解法也没好啊，最极端的情况下
: 2个点 - 〉列表长3
: 3个点 - 〉列表长7
: n个点 - 〉列表长2^n - 1.
: 这复杂度还没枚举法好啊
|
l*****g
发帖数: 49 | 46 反例很好举啊。一个边长是2R的等边三角形，它的三个顶点就不能聚到一个直径
为2R的圆内或圆周上。
【在 l*********g 的大作中提到】
: 请举个反例。
: 请举出一群点，它们之间任意两点间距离小于等于直径2R的，而它们不能聚在一个直径
: 为2R的圆内或圆周上的。请举。
: 像你这种逻辑不清的，我根本没有兴趣和你搭话。如果不是我的朋友问起是神马，我根
: 本不会理你。
|
l*********g
发帖数: 1899 | 47 谢谢提醒。
我在这个楼的2楼中的描述是我的解题思路，这个思路如果完全不加任何的refine就写
成算法的话，确实是不robust的，例如你提到的这个例子就是我的思路中的bug。但是
，正如我在这个楼的18楼中说的那样：“我认为我的思路如果写成算法，关键是如何写
好一个查找算法......”。例如，我可以在查找算法中加上一些限制，其中的限制可以
包括：如果找出来的某个组是只包含任意两点间距离皆相等并等于2R的3个点的，这个
组就无效。
【在 l*****g 的大作中提到】
: 反例很好举啊。一个边长是2R的等边三角形，它的三个顶点就不能聚到一个直径
: 为2R的圆内或圆周上。
|
g******g
发帖数: 289 | 48 还好，终于有一些明白过来了。我还以为是我逻辑不清，看把我吓的。
有时间，多跟你朋友学学，人家比你聪明太多。
【在 l*********g 的大作中提到】
: 谢谢提醒。
: 我在这个楼的2楼中的描述是我的解题思路，这个思路如果完全不加任何的refine就写
: 成算法的话，确实是不robust的，例如你提到的这个例子就是我的思路中的bug。但是
: ，正如我在这个楼的18楼中说的那样：“我认为我的思路如果写成算法，关键是如何写
: 好一个查找算法......”。例如，我可以在查找算法中加上一些限制，其中的限制可以
: 包括：如果找出来的某个组是只包含任意两点间距离皆相等并等于2R的3个点的，这个
: 组就无效。
|
n******t
发帖数: 4406 | 49 含n个点的平面点集的convex hull可以在O(nlog(n))解出来,然后包住it的最小圆可以
在O(n)时间内解出来。所以你的方法还是work的。不过，如果都想到这里，自然就会发
现没有必要解convex hull了,因为从convex hull到找最小园的用的思路也就是这个问
题的优化算法的思路了。
【在 l*********g 的大作中提到】
: 谢谢提醒。
: 我在这个楼的2楼中的描述是我的解题思路，这个思路如果完全不加任何的refine就写
: 成算法的话，确实是不robust的，例如你提到的这个例子就是我的思路中的bug。但是
: ，正如我在这个楼的18楼中说的那样：“我认为我的思路如果写成算法，关键是如何写
: 好一个查找算法......”。例如，我可以在查找算法中加上一些限制，其中的限制可以
: 包括：如果找出来的某个组是只包含任意两点间距离皆相等并等于2R的3个点的，这个
: 组就无效。
|
l*********g
发帖数: 1899 | 50 马后炮。
说句实在话，我回他的贴其实和你毫不相干的。不管他说什么，我就是为了回而回而已。
that is it.
【在 g******g 的大作中提到】
: 还好，终于有一些明白过来了。我还以为是我逻辑不清，看把我吓的。
: 有时间，多跟你朋友学学，人家比你聪明太多。
|
|
|
n******t
发帖数: 4406 | 51 同学，你不去做销售真的可惜了。
一个结果错的，复杂度估计错的，能被你说成O(N)的算法，你还有啥不能卖呢？
【在 g******g 的大作中提到】
: 还好，终于有一些明白过来了。我还以为是我逻辑不清，看把我吓的。
: 有时间，多跟你朋友学学，人家比你聪明太多。
|
g******g
发帖数: 289 | 52 按照我那个算法走，复杂度就是O(N)。如果有错误，就请指出。
我关心的是最优解法。当楼主说原题不是整数坐标，我知道我的方法不会是最优解法。
你那位的错误，我一开始就看来了，不过我一直没有说话。那么低级的错误，我也懒得
说什么。你这么聪明的人，恐怕也早已看出来了吧? 他如果不先开口骂我，我会一直保
持沉默。我说过，我关心的是最优解。
想为那位出头，还是算了吧。你是聪明人。还是教教你的朋友多学点东西，多讲点礼貌。
【在 n******t 的大作中提到】
: 同学，你不去做销售真的可惜了。
: 一个结果错的，复杂度估计错的，能被你说成O(N)的算法，你还有啥不能卖呢？
|
l*********g
发帖数: 1899 | 53 既然你这么较真，我也澄清一下。
我说你逻辑不清，是指你在5楼提出的思路。我不是指你在这个等边三角形的问题上逻
辑不清。
另外，你在40楼说：“很多时侯也许找不到一种完美算法,但是也别拿一个错误的忽悠
人。”我估计你是想指责我的思路中有那个等边三角形的bug，因此我的思路就是忽悠
人的。你说这话的时候，你认真review过你自己在这个楼里你自己的思路吗？先不说效
率，先说正确性。我也不怕告诉你，你在5楼贴出的那个想法是我在写2楼的那个帖子前
考虑过的所有方法里首先被想到过的，也是首先被我否定的。核心原因如果用俗点的话
讲就是在计算机上不管如何取那个你称作“给定点”的点，都有可能漏掉最终符合条件
的那个圆心。（这个观点ysd在他的19楼的帖子中讲得比我更具体，就是那个“一大类
CS问题的命门”那段话。）因此，你的思路的基础和根本是错误的，或者说大方向就错
了，更何谈走下去？我的等边三角形的bug可以在算法中refine，而你的思路中由于存
在我以上提到的问题，你连这样的机会都没有。你认为到底是谁在忽悠人？
我对bbs上贴出来的题（其他灌水话题不算）的答案，我自己认为不对的，我从不搭理
，例如我没有搭理你5楼的以及和5楼帖子相关的你的帖子。我去搭理一个人，哪怕我
challenge他/她，是因为我还觉得和他/她说几句是有意义的。这次我为了附和我的朋
友，不小心浪费了不少时间。
【在 g******g 的大作中提到】
: 还好，终于有一些明白过来了。我还以为是我逻辑不清，看把我吓的。
: 有时间，多跟你朋友学学，人家比你聪明太多。
|
l*********g
发帖数: 1899 | 54 我骂你什么？张全蛋？哈哈哈，你有这么红吗？
你的那个想法，就算不需要任何时间也没用。还最优解。真是笑话。
貌。
【在 g******g 的大作中提到】
: 按照我那个算法走，复杂度就是O(N)。如果有错误，就请指出。
: 我关心的是最优解法。当楼主说原题不是整数坐标，我知道我的方法不会是最优解法。
: 你那位的错误，我一开始就看来了，不过我一直没有说话。那么低级的错误，我也懒得
: 说什么。你这么聪明的人，恐怕也早已看出来了吧? 他如果不先开口骂我，我会一直保
: 持沉默。我说过，我关心的是最优解。
: 想为那位出头，还是算了吧。你是聪明人。还是教教你的朋友多学点东西，多讲点礼貌。
|
g******g
发帖数: 289 | 55 你丫别搞笑了。我在第五楼发言的时候，根本不知道坐标是不是整数，楼主是后来楼里
说的。你认识楼主？
张全蛋？那你就当吧。别生气。我没骂你。
【在 l*********g 的大作中提到】
: 既然你这么较真，我也澄清一下。
: 我说你逻辑不清，是指你在5楼提出的思路。我不是指你在这个等边三角形的问题上逻
: 辑不清。
: 另外，你在40楼说：“很多时侯也许找不到一种完美算法,但是也别拿一个错误的忽悠
: 人。”我估计你是想指责我的思路中有那个等边三角形的bug，因此我的思路就是忽悠
: 人的。你说这话的时候，你认真review过你自己在这个楼里你自己的思路吗？先不说效
: 率，先说正确性。我也不怕告诉你，你在5楼贴出的那个想法是我在写2楼的那个帖子前
: 考虑过的所有方法里首先被想到过的，也是首先被我否定的。核心原因如果用俗点的话
: 讲就是在计算机上不管如何取那个你称作“给定点”的点，都有可能漏掉最终符合条件
: 的那个圆心。（这个观点ysd在他的19楼的帖子中讲得比我更具体，就是那个“一大类
|
l*********g
发帖数: 1899 | 56 不是整数不整数的问题。是取这个点的这套方法的思想体系是错误的问题。
题目里的信息没有问题，那些点的坐标是不是整数也没有问题，不影响这个题目的解法
，也不影响你的想法是错误的。
你就不要硬凹了。
【在 g******g 的大作中提到】
: 你丫别搞笑了。我在第五楼发言的时候，根本不知道坐标是不是整数，楼主是后来楼里
: 说的。你认识楼主？
: 张全蛋？那你就当吧。别生气。我没骂你。
|
g******g
发帖数: 289 | 57 你在说什么？
如果所有位置都是整数，比如是位图，我当然可以枚举距离一个给定点小于R的所有点
，改变它们的位权值，这有问题吗？这样的操作非常快。
【在 l*********g 的大作中提到】
: 不是整数不整数的问题。是取这个点的这套方法的思想体系是错误的问题。
: 题目里的信息没有问题，那些点的坐标是不是整数也没有问题，不影响这个题目的解法
: ，也不影响你的想法是错误的。
: 你就不要硬凹了。
|
