给定n个点,选择给定列表中的一个点,使得到这一点的距离总和最小,与所有其他点相比.
距离以下列方式测量.
对于点(x,y),所有8个相邻点的距离为1.
(x+1,y)(x+1,y+1),(x+1,y-1),(x,y+1),(x,y-1),(x-1,y)(x-1,y+1),(x-1,y-1)
编辑
更清楚的解释.
函数foo定义为
foo(point_a,point_b) = max(abs(point_a.x - point_b.x),abs(point_a.y - point_b.y))
找到一个点x使得sum(list_of_points中的y的[foo(x,y)])最小.
例
输入:
12 -14
-3 3
-14 7
-14 -3
2 -12
-1 -6
产量
-1 -6
例如:(4,5)和6,7之间的距离是2.
这可以通过检查每对的总和在O(n ^ 2)时间内完成.有没有更好的算法呢？