leetcode1515 服务中心的最佳位置

思路：
是一道凸优化的问题，可以使用爬山法。
实现：
 1 class Solution
 2 {
 3 public:
 4 
 5     double getDis(double x, double y, vector<vector<int>>& p)
 6     {
 7         double sum = 0;
 8         for (int i = 0; i < p.size(); i++)
 9         {
10             sum += sqrt(pow(x - p[i][0], 2) + pow(y - p[i][1], 2));
11         }
12         return sum;
13     }
14     double getMinDistSum(vector<vector<int>>& positions)
15     {
16         int n = positions.size();
17         double x = 0, y = 0;
18         for (int i = 0; i < n; i++)
19         {
20             x += positions[i][0]; y += positions[i][1];
21         }
22         x /= n; y /= n;
23         double cur = getDis(x, y, positions), eps = 1e-7, step = 1, decay = 0.5;
24         int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
25         while (step > eps)
26         {
27             bool modified = false;
28             for (int i = 0; i < 4; i++)
29             {
30                 double nx = x + dx[i] * step, ny = y + dy[i] * step;
31                 double tmp = getDis(nx, ny, positions);
32                 if (tmp < cur)
33                 {
34                     cur = tmp;
35                     modified = true;
36                     x = nx; y = ny;
37                     break;
38                 }
39             }
40             if (!modified) step = step * (1 - decay);
41         }
42         return cur;
43     }
44 }