{"id":7751,"date":"2020-11-30T01:02:48","date_gmt":"2020-11-30T09:02:48","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7751"},"modified":"2020-11-30T01:03:11","modified_gmt":"2020-11-30T09:03:11","slug":"leetcode-1515-best-position-for-a-service-centre","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-1515-best-position-for-a-service-centre\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1515. Best Position for a Service Centre"},"content":{"rendered":"\n

A delivery company wants to build a new service centre in a new city. The company knows the positions of all the customers in this city on a 2D-Map and wants to build the new centre in a position such that the sum of the euclidean distances to all customers is minimum<\/strong>.<\/p>\n\n\n\n

Given an array positions<\/code> where positions[i] = [xi<\/sub>, yi<\/sub>]<\/code> is the position of the ith<\/code> customer on the map, return the minimum sum of the euclidean distances<\/em> to all customers.<\/p>\n\n\n\n

In other words, you need to choose the position of the service centre [xcentre<\/sub>, ycentre<\/sub>]<\/code> such that the following formula is minimized:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

Answers within 10^-5<\/code> of the actual value will be accepted.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> positions = [[0,1],[1,0],[1,2],[2,1]]\nOutput:<\/strong> 4.00000\nExplanation:<\/strong> As shown, you can see that choosing [xcentre<\/sub>, ycentre<\/sub>] = [1, 1] will make the distance to each customer = 1, the sum of all distances is 4 which is the minimum possible we can achieve.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> positions = [[1,1],[3,3]]\nOutput:<\/strong> 2.82843\nExplanation:<\/strong> The minimum possible sum of distances = sqrt(2) + sqrt(2) = 2.82843\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> positions = [[1,1]]\nOutput:<\/strong> 0.00000\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> positions = [[1,1],[0,0],[2,0]]\nOutput:<\/strong> 2.73205\nExplanation:<\/strong> At the first glance, you may think that locating the centre at [1, 0] will achieve the minimum sum, but locating it at [1, 0] will make the sum of distances = 3.\nTry to locate the centre at [1.0, 0.5773502711] you will see that the sum of distances is 2.73205.\nBe careful with the precision!\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> positions = [[0,1],[3,2],[4,5],[7,6],[8,9],[11,1],[2,12]]\nOutput:<\/strong> 32.94036\nExplanation:<\/strong> You can use [4.3460852395, 4.9813795505] as the position of the centre.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= positions.length <= 50<\/code><\/li>
  • positions[i].length == 2<\/code><\/li>
  • 0 <= positions[i][0], positions[i][1] <= 100<\/code><\/li><\/ul>\n\n\n\n
    Solution: Weiszfeld’s algorithm<\/strong><\/h2>\n\n\n\n
    Use Weiszfeld’s algorithm to compute geometric median of the samples.<\/p>\n\n\n\n
    Time complexity: O(f(epsilon) * O)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \ntemplate\ndouble dist(const vector& a, const vector& b) {\n  return sqrt((a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]));\n};\n\nclass Solution {\npublic:\n  double getMinDistSum(vector>& positions) {    \n    constexpr double kDelta = 1e-7;\n    constexpr double kEpsilon = 1e-15;\n    vector c{-1, -1};\n    double ans = 0;\n    while (true) {\n      ans = 0;\n      double nx = 0, ny = 0;\n      double denominator = 0;\n      for (const auto& p : positions) {\n        double d = dist(c, p) + kEpsilon;\n        ans += d;\n        nx += p[0] \/ d;\n        ny += p[1] \/ d;\n        denominator += 1.0 \/ d;\n      }\n      vector t{nx \/ denominator, ny \/ denominator};      \n      if (dist(c, t) < kDelta) return ans;\n      c = t;\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    A delivery company wants to build a new service centre in a new city. The company knows the positions of all the customers in this…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127],"tags":[284,217],"class_list":["post-7751","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-geometry","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7751","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7751"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7751\/revisions"}],"predecessor-version":[{"id":7753,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7751\/revisions\/7753"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7751"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7751"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7751"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}