解題說明
Best Position for a Service Centre
題目描述： 給定 n 個客戶的座標 positions[i] = [xi, yi]，找到一個服務中心的位置，使得到所有客戶的歐幾里得距離總和最小。回傳最小距離總和（精度誤差在 10^-5 以內即可）。
解題思路： 這是經典的費馬點（Fermat Point）/ 韋伯問題（Weber Problem）。距離總和函數是凸函數，可以用梯度下降法或 Weiszfeld 迭代法求解。這裡使用一種簡單的搜尋方法：從重心開始，嘗試四個方向移動，如果改善了距離總和就移動，否則縮小步長。步長不斷減半直到精度足夠。
C++ 解法
複雜度分析
時間複雜度：O(n × log(range/eps)) — 每次步長減半迭代最多 O(log(range/eps)) 次，每次計算總距離需 O(n)
空間複雜度：O(1) — 只使用常數額外空間（不計輸入）
虛擬碼
1. Initialize center (cx, cy) as the centroid of all positions
2. Set step = 100.0 (initial step size)
3. While step > epsilon:
a. Try moving in 4 directions (up, down, left, right) by step
b. If any direction reduces total distance:
- Move to new position, update bestDist
c. Else: halve the step size (step *= 0.5)
4. Return bestDist其他解法
方法二：Weiszfeld 迭代演算法 每次迭代計算新位置為 x_new = sum(xi/di) / sum(1/di)，其中 di 是當前點到第 i 個客戶的距離。收斂速度通常比梯度搜尋快，但當解恰好在某個客戶位置時可能退化。
方法三：三分搜尋 對 x 座標三分搜尋，對於每個固定的 x，再對 y 座標三分搜尋。利用距離和在每個維度上的凸性。時間複雜度 O(n × log^2(range/eps))。
延伸思考
- Weiszfeld 演算法在什麼條件下可能不收斂？如何處理退化情況？
- 如果客戶有不同的權重（例如重要客戶距離乘以更大的係數），解法需要如何修改？
- 如果需要找 2 個服務中心而不是 1 個，問題會變成什麼？（提示：考慮 k-medians 問題）