{"id":6569,"date":"2020-04-04T20:49:18","date_gmt":"2020-04-05T03:49:18","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6569"},"modified":"2020-04-04T20:50:12","modified_gmt":"2020-04-05T03:50:12","slug":"leetcode-1401-circle-and-rectangle-overlapping","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-1401-circle-and-rectangle-overlapping\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1401. Circle and Rectangle Overlapping"},"content":{"rendered":"\n

Given a circle represented as (radius<\/code>, x_center<\/code>, y_center<\/code>) and an axis-aligned rectangle represented as (x1<\/code>, y1<\/code>, x2<\/code>, y2<\/code>), where (x1<\/code>, y1<\/code>) are the coordinates of the bottom-left corner, and (x2<\/code>, y2<\/code>) are the coordinates of the top-right corner of the rectangle.<\/p>\n\n\n\n

Return True if the circle and rectangle are overlapped otherwise return False.<\/p>\n\n\n\n

In other words, check if there are any <\/strong>point (xi, yi) such that belongs to the circle and the rectangle at the same time.<\/p>\n\n\n\n

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

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1\nOutput:<\/strong> true\nExplanation:<\/strong> Circle and rectangle share the point (1,0) \n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1\nOutput:<\/strong> true\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3\nOutput:<\/strong> true\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1\nOutput:<\/strong> false\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= radius <= 2000<\/code><\/li>
  • -10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4<\/code><\/li>
  • x1 < x2<\/code><\/li>
  • y1 < y2<\/code><\/li><\/ul>\n\n\n\n
    Solution: Geometry<\/strong><\/h2>\n\n\n\n
    Find the shortest distance from the center to the rectangle, return dist <= radius.<\/p>\n\n\n\n
    Time complexity: O(1)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {\n    int dx = x_center - max(x1, min(x2, x_center));\n    int dy = y_center - max(y1, min(y2, y_center));\n    return dx * dx + dy * dy <= radius * radius;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given a circle represented as (radius, x_center, y_center) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates…<\/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,576,177,343],"class_list":["post-6569","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-circle","tag-geometry","tag-inside","tag-medium","tag-rectangle","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6569","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=6569"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6569\/revisions"}],"predecessor-version":[{"id":6571,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6569\/revisions\/6571"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6569"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6569"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6569"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}