圆和矩形是否有重叠

1401. 圆和矩形是否有重叠

给你一个以 (radius, x_center, y_center) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2)，其中 (x1, y1) 是矩形左下角的坐标，(x2, y2) 是右上角的坐标。

如果圆和矩形有重叠的部分，请你返回 True ，否则返回 False 。

换句话说，请你检测是否存在点 (xi, yi) ，它既在圆上也在矩形上（两者都包括点落在边界上的情况）。

示例 1：

输入：radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
输出：true
解释：圆和矩形有公共点 (1,0)

示例 2：

输入：radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
输出：true

示例 3：

输入：radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3
输出：true

示例 4：

输入：radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
输出：false

提示：

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) { } };

golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-06-25 09:20:23

func distance(ux, uy, vx, vy int) int {
  return (ux - vx) * (ux - vx) +  (uy - vy) * (uy - vy)
}

func checkOverlap(radius int, xCenter int, yCenter int, x1 int, y1 int, x2 int, y2 int) bool {
  // 圆心在矩形内部
  if x1 <= xCenter && xCenter <= x2 && y1 <= yCenter && yCenter <= y2 {
    return true
  }

  // 圆心在矩形上部
  if x1 <= xCenter && xCenter <= x2 && y2 <= yCenter && yCenter <= y2 + radius {
    return true
  }

  // 圆心在矩形下部
  if x1 <= xCenter && xCenter <= x2 && y1 - radius <= yCenter && yCenter <= y1 {
    return true
  }

  // 圆心在矩形左部
  if x1 - radius <= xCenter && xCenter <= x1 && y1 <= yCenter && yCenter <= y2 {
    return true
  }

  // 圆心在矩形右部
  if x2 <= xCenter && xCenter <= x2 + radius && y1 <= yCenter && yCenter <= y2 {
    return true
  }

  // 矩形左上角
  if distance(xCenter, yCenter, x1, y2) <= radius * radius {
    return true
  }

  // 矩形左下角
  if distance(xCenter, yCenter, x1, y1) <= radius * radius {
    return true
  }

  // 矩形右上角
  if distance(xCenter, yCenter, x2, y2) <= radius * radius {
    return true
  }

  // 矩形右下角
  if distance(xCenter, yCenter, x1, y2) <= radius * radius {
    return true
  }

  // 无交点
  return false
}

python3 解法, 执行用时: 40 ms, 内存消耗: 16 MB, 提交时间: 2023-06-25 09:20:06

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:

        def distance(ux, uy, vx, vy):
            return (ux - vx)**2 + (uy - vy)**2

        """
        圆心在矩形内部
        """
        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:
            return True

        """
        圆心在矩形上部
        """
        if x1 <= xCenter <= x2 and y2 <= yCenter <= y2 + radius:
            return True

        """
        圆心在矩形下部
        """
        if x1 <= xCenter <= x2 and y1 - radius <= yCenter <= y1:
            return True

        """
        圆心在矩形左部
        """
        if x1 - radius <= xCenter <= x1 and y1 <= yCenter <= y2:
            return True

        """
        圆心在矩形右部
        """
        if x2 <= xCenter <= x2 + radius and y1 <= yCenter <= y2:
            return True

        """
        矩形左上角
        """
        if distance(xCenter, yCenter, x1, y2) <= radius**2:
            return True

        """
        矩形左下角
        """
        if distance(xCenter, yCenter, x1, y1) <= radius**2:
            return True

        """
        矩形右上角
        """
        if distance(xCenter, yCenter, x2, y2) <= radius**2:
            return True

        """
        矩形右下角
        """
        if distance(xCenter, yCenter, x1, y2) <= radius**2:
            return True

        """
        无交点
        """
        return False

python3 解法, 执行用时: 36 ms, 内存消耗: 15.9 MB, 提交时间: 2023-06-25 09:19:37

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        dist = 0
        if xCenter < x1 or xCenter > x2:
            dist += min((x1 - xCenter) ** 2, (x2 - xCenter) ** 2)
        if yCenter < y1 or yCenter > y2:
            dist += min((y1 - yCenter) ** 2, (y2 - yCenter) ** 2)
        return dist <= radius ** 2

javascript 解法, 执行用时: 52 ms, 内存消耗: 41.1 MB, 提交时间: 2023-06-25 09:19:18

/**
 * @param {number} radius
 * @param {number} xCenter
 * @param {number} yCenter
 * @param {number} x1
 * @param {number} y1
 * @param {number} x2
 * @param {number} y2
 * @return {boolean}
 */
// 圆心到矩形区域最短距离
var checkOverlap = function(radius, xCenter, yCenter, x1, y1, x2, y2) {
    dist = 0;
    if (xCenter < x1 || xCenter > x2) {
        dist += Math.min(Math.pow(x1 - xCenter, 2), Math.pow(x2 - xCenter, 2));
    }
    if (yCenter < y1 || yCenter > y2) {
        dist += Math.min(Math.pow(y1 - yCenter, 2), Math.pow(y2 - yCenter, 2));
    }
    return dist <= radius ** 2;
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-06-25 09:18:34

func checkOverlap(radius int, xCenter int, yCenter int, x1 int, y1 int, x2 int, y2 int) bool {
	f := func(i, j, k int) int {
		if i <= k && k <= j {
			return 0
		}
		if k < i {
			return i - k
		}
		return k - j
	}
	a := f(x1, x2, xCenter)
	b := f(y1, y2, yCenter)
	return a*a+b*b <= radius*radius
}

java 解法, 执行用时: 0 ms, 内存消耗: 38.3 MB, 提交时间: 2023-06-25 09:18:18

class Solution {
    public boolean checkOverlap(
        int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
        int a = f(x1, x2, xCenter);
        int b = f(y1, y2, yCenter);
        return a * a + b * b <= radius * radius;
    }

    private int f(int i, int j, int k) {
        if (i <= k && k <= j) {
            return 0;
        }
        return k < i ? i - k : k - j;
    }
}

python3 解法, 执行用时: 44 ms, 内存消耗: 16 MB, 提交时间: 2023-06-25 09:18:04

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        def f(i: int, j: int, k: int) -> int:
            if i <= k <= j:
                return 0
            return i - k if k < i else k - j

        a = f(x1, x2, xCenter)
        b = f(y1, y2, yCenter)
        return a * a + b * b <= radius * radius

上一题

下一题

详情