{"id":6770,"date":"2020-05-16T22:22:56","date_gmt":"2020-05-17T05:22:56","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6770"},"modified":"2020-05-16T23:30:40","modified_gmt":"2020-05-17T06:30:40","slug":"leetcode-1453-maximum-number-of-darts-inside-of-a-circular-dartboard","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-1453-maximum-number-of-darts-inside-of-a-circular-dartboard\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1453. Maximum Number of Darts Inside of a Circular Dartboard"},"content":{"rendered":"\n<p>You have a very large square wall and a circular dartboard placed on the wall.&nbsp;You have been challenged to throw darts into the board blindfolded.&nbsp;Darts thrown at the wall are represented as an array of&nbsp;<code>points<\/code>&nbsp;on a 2D plane.&nbsp;<\/p>\n\n\n\n<p>Return&nbsp;the maximum number of points that are within or&nbsp;lie&nbsp;on&nbsp;<strong>any<\/strong>&nbsp;circular dartboard of radius&nbsp;<code>r<\/code>.<\/p>\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\/04\/29\/sample_1_1806.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> Circle dartboard with center in (0,0) and radius = 2 contain all points.\n<\/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\/2020\/04\/29\/sample_2_1806.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5\n<strong>Output:<\/strong> 5\n<strong>Explanation:<\/strong> Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).\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> points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1\n<strong>Output:<\/strong> 1\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> points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2\n<strong>Output:<\/strong> 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;= points.length &lt;= 100<\/code><\/li><li><code>points[i].length == 2<\/code><\/li><li><code>-10^4 &lt;= points[i][0], points[i][1] &lt;= 10^4<\/code><\/li><li><code>1 &lt;= r &lt;= 5000<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Angular Sweep<\/strong><\/h2>\n\n\n\n<p>See for more details: <a href=\"https:\/\/www.geeksforgeeks.org\/angular-sweep-maximum-points-can-enclosed-circle-given-radius\/\">https:\/\/www.geeksforgeeks.org\/angular-sweep-maximum-points-can-enclosed-circle-given-radius\/<\/a><\/p>\n\n\n\n<p>Time complexity: O(n^2*logn)<br>Space complexity: O(n^2)<\/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\n\/\/ Python-Like enumerate() In C++17\n\/\/ http:\/\/reedbeta.com\/blog\/python-like-enumerate-in-cpp17\/\ntemplate <typename T,\n          typename TIter = decltype(std::begin(std::declval<T>())),\n          typename = decltype(std::end(std::declval<T>()))>\nconstexpr auto enumerate(T && iterable) {\n  struct iterator {\n    size_t i;\n    TIter iter;\n    bool operator != (const iterator & other) const { return iter != other.iter; }\n    void operator ++ () { ++i; ++iter; }\n    auto operator * () const { return std::tie(i, *iter); }\n  };\n  struct iterable_wrapper {\n    T iterable;\n    auto begin() { return iterator{ 0, std::begin(iterable) }; }\n    auto end() { return iterator{ 0, std::end(iterable) }; }\n  };\n  return iterable_wrapper{ std::forward<T>(iterable) };\n}\n\nclass Solution {\npublic:\n  int numPoints(vector<vector<int>>& points, int r) {\n    const int n = points.size();\n    vector<vector<double>> d(n, vector<double>(n));\n    \n    for (const auto& [i, pi] : enumerate(points))  \n      for (const auto& [j, pj] : enumerate(points))\n        d[i][j] = d[j][i] = sqrt((pi[0] - pj[0]) * (pi[0] - pj[0]) \n                               + (pi[1] - pj[1]) * (pi[1] - pj[1]));\n        \n    int ans = 1;\n    for (const auto& [i, pi] : enumerate(points)) {    \n      vector<pair<double, int>> angles; \/\/ {angle, event_type}\n      for (const auto& [j, pj] : enumerate(points)) {\n        if (i != j && d[i][j] <= 2 * r) {\n          const double a = atan2(pj[1] - pi[1], pj[0] - pi[0]);\n          const double b = acos(d[i][j] \/ (2 * r));\n          angles.emplace_back(a - b, -1); \/\/ entering\n          angles.emplace_back(a + b, 1); \/\/ exiting\n        }\n      }\n      \/\/ If angles are the same, entering points go first.\n      sort(begin(angles), end(angles));\n      int pts = 1;\n      for (const auto&#038; [_, event] : angles)\n        ans = max(ans, pts -= event);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You have a very large square wall and a circular dartboard placed on the wall.&nbsp;You have been challenged to throw darts into the board blindfolded.&nbsp;Darts&#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":[599,575,353,217],"class_list":["post-6770","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-angular-sweep","tag-circle","tag-gemoetry","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6770","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=6770"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6770\/revisions"}],"predecessor-version":[{"id":6773,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6770\/revisions\/6773"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6770"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6770"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6770"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}