1515. Best Position for a Service Centre

题目信息

题号:

1515

难度:

Hard

主题:

计算几何、连续优化、几何中位数

原题:

LeetCode 1515

重点:

服务中心可位于平面任意实数坐标;最小化到所有给定点的欧氏距离总和

题目重述

给定平面上的若干客户位置 positions[i] = [x_i,y_i]。可以把服务中心设置在平面上的任意位置 (x,y),坐标不要求为整数。

请返回服务中心到所有客户位置的欧氏距离之和能够达到的最小值。与正确答案误差不超过 10^-5 的结果均可接受。

1 <= positions.length <= 50,坐标均位于 [0,100]。

自建示例

两个点之间的任意线段位置都达到同一最小值:

输入:positions = [[0,0],[2,0]]
输出:2.0
解释:服务中心位于两点连线段上时,两段距离之和恒为 2。

只有一个客户时可以与其重合:

输入:positions = [[7,9]]
输出:0.0
解释:把服务中心放在 (7,9) 即可使距离为零。