几何中位数
几何中位数
步骤1：** 按x维度（nlogn）对点集合进行排序 第2步： 计算每个点与所有点之间的x距离 往左边 它：
xLDist[0] := 0
for i := 1 to n - 1
xLDist[i] := xLDist[i-1] + ( ( p[i].x - p[i-1].x ) * i)
第3步： 计算每个点与所有点之间的x距离 在右边 它：
xRDist[n - 1] := 0
for i := n - 2 to 0
xRDist[i] := xRDist[i+1] + ( ( p[i+1].x - p[i].x ) * i)
步骤4： 总结两者，你将获得从每个点到其他N-1点的总x距离
for i := 0 to n - 1
p[i].xDist = xLDist[i] + xRDist[i]
用y维重复步骤1,2,3,4得到
p[i].yDist
总和最小的点 xDist 和 yDist 是答案
总复杂度O（nlogn）
进一步说明： 想法是重用已经计算的前一点的总距离。 让我们说我们有3点ABCD排序，我们看到D之前的总剩余距离是：
AD + BD + CD =（AC + CD）+（BC + CD）+ CD = AC + BC + 3CD
其中 (AC + BC) 是C之前与其他人之间的总剩余距离，我们利用了这个，只需要计算 ldist(C) + 3CD
