B*****t
发帖数: 335 | 1 给定一堆二维空间中的点. 每一个点可以算出一个价值, 找出价值最小的点.
每个点的价值为这个点与其他所有点距离中最大的那个距离.
计算点A到其他点B的距离 max(b_x-a_x, 0) + max(b_y-a_y, 0)
A的价值为max(max(b_i_x-a_x, 0) + max(b_i_y-a_y, 0)) for all i, b_i != a |
B*****t
发帖数: 335 | 2 如果坐标只取整数值, 而且限定范围, 比如 -1000
的算法? 感觉可以用SA |
B********u
发帖数: 1 | 3 昨天想了下，你找到y最大的点，过it画y轴；找到x最大的点，过it画x轴；结果会在
quadrant I里面 |
B*****t
发帖数: 335 | 4 这个搜索范围还是很大. 感觉这个点只能在边界上
【在 B********u 的大作中提到】
: 昨天想了下，你找到y最大的点，过it画y轴；找到x最大的点，过it画x轴；结果会在
: quadrant I里面
|
B********u
发帖数: 1 | 5 盲猜一个
将y值最大点跟x值最大点相连做直线，然后将此直线平移(保持斜率)，切过的最右面一
个点为所求
因为对于任意一个点，如果不动其它点，将此点往左或者往下移动，都将会增大价值
【在 B*****t 的大作中提到】
: 这个搜索范围还是很大. 感觉这个点只能在边界上
|
b******g
发帖数: 77 | |
b******g
发帖数: 77 | |
B*****t
发帖数: 335 | 8 这个是求manhattan distance最大值, 上面的问题是求minmax, 思路好像可以借鉴, 想
了想还是走不通
distinct-
【在 b******g 的大作中提到】
: https://www.geeksforgeeks.org/maximum-manhattan-distance-between-a-distinct-
: pair-from-n-coordinates/
|
B********u
发帖数: 1 | 9 解应该是过y = -x + b的点里面s.t. b最大的那个，类似于LP；就是x+y最大的点
对于任意一个点，保持其它点不动的情况下，过这点的线y = -x + b。从此点往左和往
下移动价值都会增加.往右或者往上价值都会减少，沿着此线则价值不变
考虑点X过y = -x + b1, 点B过y = -x + b2, b1 < b2.
那么相对所有点集S\{X,Y},X的价值都大于Y的价值;同时，考虑点集{X,Y},val(X) >
val(Y)。可以得出结论，y = -x + b1上的任何一点价值高于y = -x + b2上的任何一点
的价值 if b1 < b2 |
B*****t
发帖数: 335 | 10 原来如此, 高!
【在 B********u 的大作中提到】
: 解应该是过y = -x + b的点里面s.t. b最大的那个，类似于LP；就是x+y最大的点
: 对于任意一个点，保持其它点不动的情况下，过这点的线y = -x + b。从此点往左和往
: 下移动价值都会增加.往右或者往上价值都会减少，沿着此线则价值不变
: 考虑点X过y = -x + b1, 点B过y = -x + b2, b1 < b2.
: 那么相对所有点集S\{X,Y},X的价值都大于Y的价值;同时，考虑点集{X,Y},val(X) >
: val(Y)。可以得出结论，y = -x + b1上的任何一点价值高于y = -x + b2上的任何一点
: 的价值 if b1 < b2
|
B********u
发帖数: 1 | 11 结果是错误的
(13, 46), (41, 34), (49, 28)这三个点, min_value应该是12，from （41，34）,
not 18, from (49, 28)
模拟了一下大概80%能找到精确解，20%找到是错误的次优解
【在 B*****t 的大作中提到】
: 原来如此, 高!
|
m***g
发帖数: 1 | 12 可不可以这样算，求出一个虚拟的均值点Pe: (Xe,Ye)=( (X1+X2+...+Xn)/n, (Y1+
Y2+...+Yn)/n)
，来代替所有的点, 然后求各个点到这个点的值，值最小：max(max(Xi -Xe, 0), max(
Yi-Ye, 0)). 虽然这样算出来的值不是真正的最小值，但这样找出来的点是最小值的点。
以前面的点为例：(13, 46), (41, 34), (49, 28)
Pe:(103/3, 108/3) 约为（(34, 36)
各个点到这个点距离：0 :10，7: 0，15: 0
7为最小值，因此可得出点（41，34）为所求的点。真实的值为12。 |
m***g
发帖数: 1 | 13 如果这些值都在边界上，可以采用bounding box 的方法，如果再简单点，算包含所有
点的凸多边形convex hull.
Bounding box:
https://github.com/cansik/LongLiveTheSquare
Convex hull:
https://en.m.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_
hull/Monotone_chain
: 这个搜索范围还是很大. 感觉这个点只能在边界上
【在 B*****t 的大作中提到】
: 原来如此, 高!
|
d********e
发帖数: 321 | 14 几乎肯定是需要 O(n^2)复杂度，把每个点算出和其他点的距离呗
【在 B*****t 的大作中提到】
: 给定一堆二维空间中的点. 每一个点可以算出一个价值, 找出价值最小的点.
: 每个点的价值为这个点与其他所有点距离中最大的那个距离.
: 计算点A到其他点B的距离 max(b_x-a_x, 0) + max(b_y-a_y, 0)
: A的价值为max(max(b_i_x-a_x, 0) + max(b_i_y-a_y, 0)) for all i, b_i != a
|
l****0
发帖数: 1032 | 15 所以按照这个价值的公式，如果最右上有一个点，那么它的价值为0
是这样吗？ |
s********d
发帖数: 162 | 16 是距离[max(x), max(y)] manhattan distance 最小的那个点么？ |
s********d
发帖数: 162 | 17 min( max(max(x) - x_i, max(y) - y_i ) ) , 这个呢？ |
j****t
发帖数: 131 | 18 瞎想了一下，最大值应该是到几个边界点的距离，这个我不会推导
边界点是 MAX(X + Y) , MIN(X+Y) , MAX(-X+Y),MIN(-X-Y) 的 4 个点，
求以上 MAX 和 MIN 是 O(N),
计算value 也是 O(N)
求最小值 也是 O(N)
复杂度应该是O(N) |
B*****t
发帖数: 335 | 19 给定一堆二维空间中的点. 每一个点可以算出一个价值, 找出价值最小的点.
每个点的价值为这个点与其他所有点距离中最大的那个距离.
计算点A到其他点B的距离 max(b_x-a_x, 0) + max(b_y-a_y, 0)
A的价值为max(max(b_i_x-a_x, 0) + max(b_i_y-a_y, 0)) for all i, b_i != a |
B*****t
发帖数: 335 | 20 如果坐标只取整数值, 而且限定范围, 比如 -1000
的算法? 感觉可以用SA |
B********u
发帖数: 1 | 21 昨天想了下，你找到y最大的点，过it画y轴；找到x最大的点，过it画x轴；结果会在
quadrant I里面 |
B*****t
发帖数: 335 | 22 这个搜索范围还是很大. 感觉这个点只能在边界上
【在 B********u 的大作中提到】
: 昨天想了下，你找到y最大的点，过it画y轴；找到x最大的点，过it画x轴；结果会在
: quadrant I里面
|
B********u
发帖数: 1 | 23 盲猜一个
将y值最大点跟x值最大点相连做直线，然后将此直线平移(保持斜率)，切过的最右面一
个点为所求
因为对于任意一个点，如果不动其它点，将此点往左或者往下移动，都将会增大价值
【在 B*****t 的大作中提到】
: 这个搜索范围还是很大. 感觉这个点只能在边界上
|
b******g
发帖数: 77 | |
b******g
发帖数: 77 | |
B*****t
发帖数: 335 | 26 这个是求manhattan distance最大值, 上面的问题是求minmax, 思路好像可以借鉴, 想
了想还是走不通
distinct-
【在 b******g 的大作中提到】
: https://www.geeksforgeeks.org/maximum-manhattan-distance-between-a-distinct-
: pair-from-n-coordinates/
|
B********u
发帖数: 1 | 27 解应该是过y = -x + b的点里面s.t. b最大的那个，类似于LP；就是x+y最大的点
对于任意一个点，保持其它点不动的情况下，过这点的线y = -x + b。从此点往左和往
下移动价值都会增加.往右或者往上价值都会减少，沿着此线则价值不变
考虑点X过y = -x + b1, 点B过y = -x + b2, b1 < b2.
那么相对所有点集S\{X,Y},X的价值都大于Y的价值;同时，考虑点集{X,Y},val(X) >
val(Y)。可以得出结论，y = -x + b1上的任何一点价值高于y = -x + b2上的任何一点
的价值 if b1 < b2 |
B*****t
发帖数: 335 | 28 原来如此, 高!
【在 B********u 的大作中提到】
: 解应该是过y = -x + b的点里面s.t. b最大的那个，类似于LP；就是x+y最大的点
: 对于任意一个点，保持其它点不动的情况下，过这点的线y = -x + b。从此点往左和往
: 下移动价值都会增加.往右或者往上价值都会减少，沿着此线则价值不变
: 考虑点X过y = -x + b1, 点B过y = -x + b2, b1 < b2.
: 那么相对所有点集S\{X,Y},X的价值都大于Y的价值;同时，考虑点集{X,Y},val(X) >
: val(Y)。可以得出结论，y = -x + b1上的任何一点价值高于y = -x + b2上的任何一点
: 的价值 if b1 < b2
|
B********u
发帖数: 1 | 29 结果是错误的
(13, 46), (41, 34), (49, 28)这三个点, min_value应该是12，from （41，34）,
not 18, from (49, 28)
模拟了一下大概80%能找到精确解，20%找到是错误的次优解
【在 B*****t 的大作中提到】
: 原来如此, 高!
|
m***g
发帖数: 1 | 30 可不可以这样算，求出一个虚拟的均值点Pe: (Xe,Ye)=( (X1+X2+...+Xn)/n, (Y1+
Y2+...+Yn)/n)
，来代替所有的点, 然后求各个点到这个点的值，值最小：max(max(Xi -Xe, 0), max(
Yi-Ye, 0)). 虽然这样算出来的值不是真正的最小值，但这样找出来的点是最小值的点。
以前面的点为例：(13, 46), (41, 34), (49, 28)
Pe:(103/3, 108/3) 约为（(34, 36)
各个点到这个点距离：0 :10，7: 0，15: 0
7为最小值，因此可得出点（41，34）为所求的点。真实的值为12。 |
m***g
发帖数: 1 | 31 如果这些值都在边界上，可以采用bounding box 的方法，如果再简单点，算包含所有
点的凸多边形convex hull.
Bounding box:
https://github.com/cansik/LongLiveTheSquare
Convex hull:
https://en.m.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_
hull/Monotone_chain
: 这个搜索范围还是很大. 感觉这个点只能在边界上
【在 B*****t 的大作中提到】
: 原来如此, 高!
|
d********e
发帖数: 321 | 32 几乎肯定是需要 O(n^2)复杂度，把每个点算出和其他点的距离呗
【在 B*****t 的大作中提到】
: 给定一堆二维空间中的点. 每一个点可以算出一个价值, 找出价值最小的点.
: 每个点的价值为这个点与其他所有点距离中最大的那个距离.
: 计算点A到其他点B的距离 max(b_x-a_x, 0) + max(b_y-a_y, 0)
: A的价值为max(max(b_i_x-a_x, 0) + max(b_i_y-a_y, 0)) for all i, b_i != a
|
l****0
发帖数: 1032 | 33 所以按照这个价值的公式，如果最右上有一个点，那么它的价值为0
是这样吗？ |
s********d
发帖数: 162 | 34 min( max(x_max - x, y_max - y ) for x, y in ... ) |
j****t
发帖数: 131 | 35 瞎想了一下，最大值应该是到几个边界点的距离，这个我不会推导
边界点是 MAX(X + Y) , MIN(X+Y) , MAX(-X+Y),MIN(-X-Y) 的 4 个点，
求以上 MAX 和 MIN 是 O(N),
计算value 也是 O(N)
求最小值 也是 O(N)
复杂度应该是O(N) |
b***e
发帖数: 1419 | 36 定义： B点包含A点如果X_A < X_B 并且 Y_A < Y_B。
定理1： 如果B包含A，那么对于任何点C，Dist(A, C) >= Dist (B, C)。
证明： 基本上废话。
由于定理1，所有被其它点包含的点不可能是价值最小的点。所以第一步我们先找出那
些不被任何点包含的点。这个排序就可以了。
第一步： 对每个点以（Y， X） 从大到小排序。如果Y大则排在前面。如果Y一样则X大
的排前面。
第二步： 对拍好序的点扫一遍。 先把打头的设为头牌。 从第二个点开始，如果目前
点被头牌包含，则扔掉，一直找到一个不被头牌包含的，设其为新的头牌。继续直至所
有的点被扫描。 得到系列头牌。
第三步： 这些得到的头牌们就是candidates。每个头牌的价值是它到第一头牌的距离
和最后头牌的距离里较大的那个。扫一遍头牌们就找到了最小价值点。
进一步优化：
第一步，如果两个点的Y一样，我们留下X值大的那个，另外一个直接扔掉。
第三步，其实头牌的价值是伪单调的，就是先降后升。所以可以用二分法追求极致的效
率。
这个是实际中的问题，还是人为制造的。如果是实际中的问题我可以给更详细的解释。 |
s********d
发帖数: 162 | 37 楼上的推理的思路是跟我的很相似
我觉得我在之前给出的答案是对的
具体用反证法证明
1）找到的点是距离最小的点
2）算出来的值就是那个点的价值 |
b***e
发帖数: 1419 | 38 对，我其实是提供了对你的那个算法的一个证明。这个问题不需要排序，O(n)可以解决。
【在 s********d 的大作中提到】
: 楼上的推理的思路是跟我的很相似
: 我觉得我在之前给出的答案是对的
: 具体用反证法证明
: 1）找到的点是距离最小的点
: 2）算出来的值就是那个点的价值
|
