1515. Best Position for a Service Centre¶
题目信息¶
- 题号:
1515
- 难度:
Hard
- 主题:
计算几何、连续优化、几何中位数
- 原题:
- 重点:
服务中心可位于平面任意实数坐标;最小化到所有给定点的欧氏距离总和
题目重述¶
给定平面上的若干客户位置 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) 即可使距离为零。