{"id":8357,"date":"2021-04-17T11:57:55","date_gmt":"2021-04-17T18:57:55","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8357"},"modified":"2021-04-17T12:05:38","modified_gmt":"2021-04-17T19:05:38","slug":"leetcode-1828-queries-on-number-of-points-inside-a-circle","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-1828-queries-on-number-of-points-inside-a-circle\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1828. Queries on Number of Points Inside a Circle"},"content":{"rendered":"\n

You are given an array points<\/code> where points[i] = [xi<\/sub>, yi<\/sub>]<\/code> is the coordinates of the ith<\/sup><\/code> point on a 2D plane. Multiple points can have the same<\/strong> coordinates.<\/p>\n\n\n\n

You are also given an array queries<\/code> where queries[j] = [xj<\/sub>, yj<\/sub>, rj<\/sub>]<\/code> describes a circle centered at (xj<\/sub>, yj<\/sub>)<\/code> with a radius of rj<\/sub><\/code>.<\/p>\n\n\n\n

For each query queries[j]<\/code>, compute the number of points inside<\/strong> the jth<\/sup><\/code> circle. Points on the border<\/strong> of the circle are considered inside<\/strong>.<\/p>\n\n\n\n

Return an array <\/em>answer<\/code>, where <\/em>answer[j]<\/code> is the answer to the <\/em>jth<\/sup><\/code> query<\/em>.<\/p>\n\n\n\n

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

Input:<\/strong> points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]\nOutput:<\/strong> [3,2,2]\nExplanation: <\/strong>The points and circles are shown above.\nqueries[0] is the green circle, queries[1] is the red circle, and queries[2] is the blue circle.\n<\/pre>\n\n\n\n
Example 2:<\/strong>\"\"<\/p>\n\n\n\n
Input:<\/strong> points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]\nOutput:<\/strong> [2,3,2,4]\nExplanation: <\/strong>The points and circles are shown above.\nqueries[0] is green, queries[1] is red, queries[2] is blue, and queries[3] is purple.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= points.length <= 500<\/code><\/li>
  • points[i].length == 2<\/code><\/li>
  • 0 <= x\u200b\u200b\u200b\u200b\u200b\u200bi<\/sub>, y\u200b\u200b\u200b\u200b\u200b\u200bi<\/sub> <= 500<\/code><\/li>
  • 1 <= queries.length <= 500<\/code><\/li>
  • queries[j].length == 3<\/code><\/li>
  • 0 <= xj<\/sub>, yj<\/sub> <= 500<\/code><\/li>
  • 1 <= rj<\/sub> <= 500<\/code><\/li>
  • All coordinates are integers.<\/li><\/ul>\n\n\n\n
    Solution: Brute Force<\/strong><\/h2>\n\n\n\n
    Time complexity: O(P * Q)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector countPoints(vector>& points, vector>& queries) {\n    vector ans;\n    ans.reserve(queries.size());\n    for (const auto& q : queries) {\n      const int rs = q[2] * q[2];\n      int cnt = 0;      \n      for (const auto& p : points)\n        if ((q[0] - p[0]) * (q[0] - p[0]) + \n            (q[1] - p[1]) * (q[1] - p[1]) <= rs)\n          ++cnt;\n      ans.push_back(cnt);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an array points where points[i] = [xi, yi] is the coordinates of the ith point on a 2D plane. Multiple points can have the same coordinates. You are also given…<\/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":[575,284,177],"class_list":["post-8357","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-circle","tag-geometry","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8357","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=8357"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8357\/revisions"}],"predecessor-version":[{"id":8359,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8357\/revisions\/8359"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8357"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8357"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8357"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}