{"id":7516,"date":"2020-10-17T13:29:03","date_gmt":"2020-10-17T20:29:03","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7516"},"modified":"2020-10-17T13:32:24","modified_gmt":"2020-10-17T20:32:24","slug":"leetcode-1620-coordinate-with-maximum-network-quality","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-1620-coordinate-with-maximum-network-quality\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1620. Coordinate With Maximum Network Quality"},"content":{"rendered":"\n<p>You are given an array of network towers&nbsp;<code>towers<\/code>&nbsp;and an integer&nbsp;<code>radius<\/code>, where&nbsp;<code>towers[i] = [x<sub>i<\/sub>, y<sub>i<\/sub>, q<sub>i<\/sub>]<\/code>&nbsp;denotes the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;network tower with location&nbsp;<code>(x<sub>i<\/sub>, y<sub>i<\/sub>)<\/code>&nbsp;and quality factor&nbsp;<code>q<sub>i<\/sub><\/code>. All the coordinates are&nbsp;<strong>integral coordinates<\/strong>&nbsp;on the X-Y plane, and the distance between two coordinates is the&nbsp;<strong>Euclidean distance<\/strong>.<\/p>\n\n\n\n<p>The integer&nbsp;<code>radius<\/code>&nbsp;denotes the&nbsp;<strong>maximum distance<\/strong>&nbsp;in which the tower is&nbsp;<strong>reachable<\/strong>. The tower is&nbsp;<strong>reachable<\/strong>&nbsp;if the distance is less than or equal to&nbsp;<code>radius<\/code>. Outside that distance, the signal becomes garbled, and the tower is&nbsp;<strong>not reachable<\/strong>.<\/p>\n\n\n\n<p>The signal quality of the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;tower at a coordinate&nbsp;<code>(x, y)<\/code>&nbsp;is calculated with the formula&nbsp;<code>\u230aq<sub>i<\/sub>&nbsp;\/ (1 + d)\u230b<\/code>, where&nbsp;<code>d<\/code>&nbsp;is the distance between the tower and the coordinate. The&nbsp;<strong>network quality<\/strong>&nbsp;at a coordinate is the sum of the signal qualities from all the&nbsp;<strong>reachable<\/strong>&nbsp;towers.<\/p>\n\n\n\n<p>Return&nbsp;<em>the integral coordinate where the&nbsp;<strong>network quality<\/strong>&nbsp;is maximum<\/em>. If there are multiple coordinates with the same&nbsp;<strong>network quality<\/strong>, return&nbsp;<em>the lexicographically minimum coordinate<\/em>.<\/p>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>A coordinate&nbsp;<code>(x1, y1)<\/code>&nbsp;is lexicographically smaller than&nbsp;<code>(x2, y2)<\/code>&nbsp;if either&nbsp;<code>x1 &lt; x2<\/code>&nbsp;or&nbsp;<code>x1 == x2<\/code>&nbsp;and&nbsp;<code>y1 &lt; y2<\/code>.<\/li><li><code>\u230aval\u230b<\/code>&nbsp;is the greatest integer less than or equal to&nbsp;<code>val<\/code>&nbsp;(the floor function).<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/09\/22\/untitled-diagram.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2\n<strong>Output:<\/strong> [2,1]\n<strong>Explanation: <\/strong>\nAt coordinate (2, 1) the total quality is 13\n- Quality of 7 from (2, 1) results in \u230a7 \/ (1 + sqrt(0)\u230b = \u230a7\u230b = 7\n- Quality of 5 from (1, 2) results in \u230a5 \/ (1 + sqrt(2)\u230b = \u230a2.07\u230b = 2\n- Quality of 9 from (3, 1) results in \u230a9 \/ (1 + sqrt(1)\u230b = \u230a4.5\u230b = 4\nNo other coordinate has higher quality.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> towers = [[23,11,21]], radius = 9\n<strong>Output:<\/strong> [23,11]\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2\n<strong>Output:<\/strong> [1,2]\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> towers = [[2,1,9],[0,1,9]], radius = 2\n<strong>Output:<\/strong> [0,1]\n<strong>Explanation: <\/strong>Both (0, 1) and (2, 1) are optimal in terms of quality but (0, 1) is lexicograpically minimal.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= towers.length &lt;= 50<\/code><\/li><li><code>towers[i].length == 3<\/code><\/li><li><code>0 &lt;= x<sub>i<\/sub>, y<sub>i<\/sub>, q<sub>i<\/sub>&nbsp;&lt;= 50<\/code><\/li><li><code>1 &lt;= radius &lt;= 50<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Brute Force<\/strong><\/h2>\n\n\n\n<p>Try all possible coordinates from (0, 0) to (50, 50).<\/p>\n\n\n\n<p>Time complexity: O(|X|*|Y|*t)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {\n    constexpr int n = 50;\n    vector<int> ans;\n    int max_q = 0;    \n    for (int x = 0; x <= n; ++x)\n      for (int y = 0; y <= n; ++y) {\n        int q = 0;\n        for (const auto&#038; tower : towers) {\n          const int tx = tower[0], ty = tower[1];\n          const float d = sqrt((x - tx) * (x - tx) + (y - ty) * (y - ty));\n          if (d > radius) continue;\n          q += floor(tower[2] \/ (1 + d));\n        }\n        if (q > max_q) {\n          max_q = q;\n          ans = {x, y};\n        }\n      }    \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an array of network towers&nbsp;towers&nbsp;and an integer&nbsp;radius, where&nbsp;towers[i] = [xi, yi, qi]&nbsp;denotes the&nbsp;ith&nbsp;network tower with location&nbsp;(xi, yi)&nbsp;and quality factor&nbsp;qi. All the coordinates&#8230;<\/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":[106,353,177],"class_list":["post-7516","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-brute-force","tag-gemoetry","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7516","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=7516"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7516\/revisions"}],"predecessor-version":[{"id":7518,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7516\/revisions\/7518"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7516"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7516"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7516"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}