{"id":9688,"date":"2022-04-27T08:57:22","date_gmt":"2022-04-27T15:57:22","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9688"},"modified":"2022-04-27T08:57:45","modified_gmt":"2022-04-27T15:57:45","slug":"leetcode-2249-count-lattice-points-inside-a-circle","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-2249-count-lattice-points-inside-a-circle\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2249. Count Lattice Points Inside a Circle"},"content":{"rendered":"\n<p>Given a 2D integer array&nbsp;<code>circles<\/code>&nbsp;where&nbsp;<code>circles[i] = [x<sub>i<\/sub>, y<sub>i<\/sub>, r<sub>i<\/sub>]<\/code>&nbsp;represents the center&nbsp;<code>(x<sub>i<\/sub>, y<sub>i<\/sub>)<\/code>&nbsp;and radius&nbsp;<code>r<sub>i<\/sub><\/code>&nbsp;of the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;circle drawn on a grid, return&nbsp;<em>the&nbsp;<strong>number of lattice points<\/strong>&nbsp;<\/em><em>that are present inside&nbsp;<strong>at least one<\/strong>&nbsp;circle<\/em>.<\/p>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>A&nbsp;<strong>lattice point<\/strong>&nbsp;is a point with integer coordinates.<\/li><li>Points that lie&nbsp;<strong>on the circumference of a circle<\/strong>&nbsp;are also considered to be inside it.<\/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\/2022\/03\/02\/exa-11.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> circles = [[2,2,1]]\n<strong>Output:<\/strong> 5\n<strong>Explanation:<\/strong>\nThe figure above shows the given circle.\nThe lattice points present inside the circle are (1, 2), (2, 1), (2, 2), (2, 3), and (3, 2) and are shown in green.\nOther points such as (1, 1) and (1, 3), which are shown in red, are not considered inside the circle.\nHence, the number of lattice points present inside at least one circle is 5.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2022\/03\/02\/exa-22.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> circles = [[2,2,2],[3,4,1]]\n<strong>Output:<\/strong> 16\n<strong>Explanation:<\/strong>\nThe figure above shows the given circles.\nThere are exactly 16 lattice points which are present inside at least one circle. \nSome of them are (0, 2), (2, 0), (2, 4), (3, 2), and (4, 4).\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= circles.length &lt;= 200<\/code><\/li><li><code>circles[i].length == 3<\/code><\/li><li><code>1 &lt;= x<sub>i<\/sub>, y<sub>i<\/sub>&nbsp;&lt;= 100<\/code><\/li><li><code>1 &lt;= r<sub>i<\/sub>&nbsp;&lt;= min(x<sub>i<\/sub>, y<sub>i<\/sub>)<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Brute Force<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(m * m * n) = O(200 * 200 * 200)<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++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int countLatticePoints(vector<vector<int>>& circles) {\n    auto isIn = [](int u, int v, int x, int y, int r) {\n      return (u - x) * (u - x) + (v - y) * (v - y) <= r * r;\n    };    \n    int ans = 0;\n    for (int u = 0; u <= 200; ++u)\n      for (int v = 0; v <= 200; ++v) {\n        bool found = false;\n        for (const auto&#038; c : circles)\n          if (isIn(u, v, c[0], c[1], c[2])) {\n            found = true;\n            break;\n          }\n        ans += found;\n      }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a 2D integer array&nbsp;circles&nbsp;where&nbsp;circles[i] = [xi, yi, ri]&nbsp;represents the center&nbsp;(xi, yi)&nbsp;and radius&nbsp;ri&nbsp;of the&nbsp;ith&nbsp;circle drawn on a grid, return&nbsp;the&nbsp;number of lattice points&nbsp;that are present inside&nbsp;at&#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,284,177],"class_list":["post-9688","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-brute-force","tag-geometry","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9688","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=9688"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9688\/revisions"}],"predecessor-version":[{"id":9690,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9688\/revisions\/9690"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9688"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9688"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9688"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}