LeetCode1515 服务中心的最佳位置

一家快递公司希望在新城市建立新的服务中心。公司统计了该城市所有客户在二维地图上的坐标，并希望能够以此为依据为新的服务中心选址：使服务中心 到所有客户的欧几里得距离的总和最小 。

给你一个数组 positions ，其中 positions[i] = [xi, yi] 表示第 i 个客户在二维地图上的位置，返回到所有客户的 欧几里得距离的最小总和 。

换句话说，请你为服务中心选址，该位置的坐标 [xcentre, ycentre] 需要使下面的公式取到最小值：

与真实值误差在 10^-5 之内的答案将被视作正确答案。

示例 1：

输入：positions = [[0,1],[1,0],[1,2],[2,1]]
输出：4.00000
解释：如图所示，你可以选 [xcentre, ycentre] = [1, 1] 作为新中心的位置，这样一来到每个客户的距离就都是 1，所有距离之和为 4 ，这也是可以找到的最小值。

分析：这是一道经典的三分套三分的题目。我们要求最优的（x,y）到其他点的距离和最小。

对于外层三分，我们三分出x的坐标，内层三分，我们三分出y的坐标

所以要证明对于外层三分，我们要证明函数x在f(x,y)在内是凸函数，对于内层三分，我们要证明x固定，y在f(x0, y)是凸函数。

内层三分只有一个变量，直接求二阶导即可，外层三分有2个变量，但是发现有个定理可以直接使用，所以直接证明内层即可，求导即可。

内层三分证明：

由于距离和公式可以表达为如下：

对其求二阶偏导，可以证明其固定x或者y，对于y和x的二阶偏导>0，即为凸函数。可以使用三分法。

外层三分证明：

还需要证明以下函数是凸函数，因为固定x的时候，y的取值不是定值，所以

维基百科发现这个是个定理，可以直接用（）

代码：

class Solution {
public:
    vector<vector<int>> points;
    
    double get_sum(double x, double y) {
        double ans = 0;
        for (auto &p:points) {
            ans += sqrt((p[0] - x) * (p[0] - x) + (p[1] - y) * (p[1] - y));
        }
        return ans;
    }

    double calc(double x) {
        double l = 0, r = 100;
        while (r - l > 1e-7) {
            double y1 = l + (r - l) / 3, y2 = l + (r - l) / 3 * 2;
            if (get_sum(x, y1) > get_sum(x, y2)) l = y1;
            else r = y2;
        }
        return get_sum(x, r);
    }

    double getMinDistSum(vector<vector<int>>& positions) {
        points = positions;
        double l = 0, r = 100;
        while (r - l > 1e-7) {
            double x1 = l + (r - l) / 3, x2 = l + (r - l) / 3 * 2;
            if (calc(x1) > calc(x2))
                l = x1;
            else 
                r = x2;
        }
        return calc(r);
    }
};