Simulated annealing LeetCode 1515. Best Position for a Service Centre

1515. Best Position for a Service Centre

From the mathematic’s point of view, this problem is related to the Fermat point. We have a similar problem to this leetcode problem as shown in [2]. The solution of the problem shown in [2] can be found in [1].

We can use the simulated annealing algorithm to solve this problem. The code from Aoxiang Cui can be found HERE:

struct Point{double x, y;};
class Solution {
public:
    double sqr(double x)
    {
        return x*x;
    }
    double get_dis(vector<Point> & points, Point c)
    {
        auto x= c.x, y = c.y;
        double ret = 0.0;
        for (auto p :points)
        {
            auto px=p.x,  py = p.y;
            ret += sqrt(sqr(px-x)+sqr(py-y));
        }
        return ret;
    }
    
    double getMinDistSum(vector<vector<int>>&p)
    {
        const int n = p.size();
        vector<Point> points(n);
        for (int i=0;i<n;++i)
        {
            points[i] = {(double)p[i][0], (double)p[i][1]};
        }
        Point c = {0, 0};
        for (auto point:points)
        {
            c.x += point.x;
            c.y += point.y;
        }
        c.x /= n;
        c.y /= n;
        for(double step = 50.0; step>1e-7;)
        {
            bool found = false;
            Point u = {c.x+step, c.y};
            if (get_dis(points, u) < get_dis(points, c)) c = u, found=true;
            u = {c.x-step, c.y};
            if (get_dis(points, u) < get_dis(points, c)) c = u, found=true;
            u = {c.x, c.y+step};
            if (get_dis(points, u) < get_dis(points, c)) c = u, found=true;
            u = {c.x, c.y-step};
            if (get_dis(points, u) < get_dis(points, c)) c = u, found=true;
            if (!found) step /= 2.;
        }
        return get_dis(points, c);
    }
};

Reference

[1]https://www.cnblogs.com/liyinggang/p/5778919.html

[2]http://poj.org/problem?id=2420