Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1401.html

1401. Circle and Rectangle Overlapping (Medium)

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 of the top-right corner of the rectangle.

Return True if the circle and rectangle are overlapped otherwise return False.

In other words, check if there are any point (xi, yi) such that belongs to the circle and the rectangle at the same time.

 

Example 1:

Input: radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
Output: true
Explanation: Circle and rectangle share the point (1,0) 

Example 2:

Input: radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
Output: true

Example 3:

Input: radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3
Output: true

Example 4:

Input: radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
Output: false

 

Constraints:

• 1 <= radius <= 2000
• -10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4
• x1 < x2
• y1 < y2

Related Topics:
Geometry

Solution 1.

Move the center of the circle to the coordinate origin (0, 0), then this problem becomes “is there a point (x, y) (x1 <= x <= x2, y1 <= y <= y2) satisfying x^2 + y^2 <= r^2”.

So just compute minimum values of x^2 and y^2, then compare the sum with r^2..

// OJ: https://leetcode.com/problems/circle-and-rectangle-overlapping/
// Time: O(1)
// Space: O(1)
class Solution {
public:
    bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
        x1 -= x_center; x2 -= x_center;
        y1 -= y_center; y2 -= y_center;
        int minX = x1 * x2 > 0 ? min(x1*x1, x2*x2) : 0, minY = y1 * y2 > 0 ? min(y1*y1, y2*y2) : 0;
        return minY + minX <= radius * radius;
    }
};

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public boolean checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
          if (x_center >= x1 && x_center <= x2 && y_center >= y1 && y_center <= y2)
              return true;
          if (x_center >= x1 && x_center <= x2)
              return y_center >= y1 - radius && y_center <= y2 + radius;
          if (y_center >= y1 && y_center <= y2)
              return x_center >= x1 - radius && x_center <= x2 + radius;
          if (x_center < x1 && y_center < y1) {
              int distanceSquare = distanceSquare(x_center, y_center, x1, y1);
              return distanceSquare <= radius * radius;
          } else if (x_center < x1 && y_center > y2) {
              int distanceSquare = distanceSquare(x_center, y_center, x1, y2);
              return distanceSquare <= radius * radius;
          } else if (x_center > x2 && y_center < y1) {
              int distanceSquare = distanceSquare(x_center, y_center, x2, y1);
              return distanceSquare <= radius * radius;
          } else if (x_center > x2 && y_center > y2) {
              int distanceSquare = distanceSquare(x_center, y_center, x2, y2);
              return distanceSquare <= radius * radius;
          } else
              return false;
      }
  
      public int distanceSquare(int x1, int y1, int x2, int y2) {
          return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
      }
  }
  
  ############
  
  class Solution {
      public boolean checkOverlap(
          int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
          int dx = x1 > xCenter ? x1 - xCenter : (x2 < xCenter ? xCenter - x2 : 0);
          int dy = y1 > yCenter ? y1 - yCenter : (y2 < yCenter ? yCenter - y2 : 0);
          return dx * dx + dy * dy <= radius * radius;
      }
  }
  

• // OJ: https://leetcode.com/problems/circle-and-rectangle-overlapping/
  // Time: O(1)
  // Space: O(1)
  class Solution {
  public:
      bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
          x1 -= x_center; x2 -= x_center;
          y1 -= y_center; y2 -= y_center;
          int minX = x1 * x2 > 0 ? min(x1*x1, x2*x2) : 0, minY = y1 * y2 > 0 ? min(y1*y1, y2*y2) : 0;
          return minY + minX <= radius * radius;
      }
  };
  

• class Solution:
      def checkOverlap(
          self,
          radius: int,
          xCenter: int,
          yCenter: int,
          x1: int,
          y1: int,
          x2: int,
          y2: int,
      ) -> bool:
          dx = dy = 0
          if x1 > xCenter:
              dx = xCenter - x1
          elif x2 < xCenter:
              dx = xCenter - x2
          if y1 > yCenter:
              dy = yCenter - y1
          elif y2 < yCenter:
              dy = yCenter - y2
          return dx * dx + dy * dy <= radius * radius
  
  
  

• func checkOverlap(radius int, xCenter int, yCenter int, x1 int, y1 int, x2 int, y2 int) bool {
  	dx, dy := 0, 0
  	if x1 > xCenter {
  		dx = x1 - xCenter
  	} else if x2 < xCenter {
  		dx = x2 - xCenter
  	}
  	if y1 > yCenter {
  		dy = y1 - yCenter
  	} else if y2 < yCenter {
  		dy = y2 - yCenter
  	}
  	return dx*dx+dy*dy <= radius*radius
  }
  

• function checkOverlap(
      radius: number,
      xCenter: number,
      yCenter: number,
      x1: number,
      y1: number,
      x2: number,
      y2: number,
  ): boolean {
      const f = (i: number, j: number, k: number) => {
          if (i <= k && k <= j) {
              return 0;
          }
          return k < i ? i - k : k - j;
      };
      const a = f(x1, x2, xCenter);
      const b = f(y1, y2, yCenter);
      return a * a + b * b <= radius * radius;
  }
  
  

All Problems

All Solutions