leetcode：LCP 42. 玩具套圈【数据范围优化模拟集合题】

分析

这道题有一个隐含的条件就是都是整点，这个可以从数据的定义里面看出int
第二个就是这个半径小于10，暗示着我们可以尝试一下枚举

这道题要保证小圆被大圆包含：核心公式就一条|o1o2| <= r1 - r2
由于避开小数，我们可以更改为平方形式

无脑两重for

class Solution:
    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:
        # |o1o2| <= r1 - r2
        ans = 0
        for x1, y1, r1 in toys:
            for x2, y2 in circles:
                if r >= r1 and (x1 - x2) ** 2 + (y1 - y2) ** 2 <= (r - r1) ** 2:
                    ans += 1
                    break
        return ans
1
2
3
4
5
6
7
8
9
10

这个想法是朴素的，但10 ** 8会超时

优化解法

由于半径有限制，那么我们先把circles的圆心全部记录下来
再一个个toy的遍历
必须满足toy的半径更小
同时当前toy的圆心和可能满足条件的circle的圆心的举例必须是小于等于r - r_toy的
否则toy是不可能被circle包含
因此根据这个关键的条件，我们可以枚举出toy圆心上下左右最多不超过400个整点(20 * 20)
这个复杂度就是10000 * 400 = 4 * (10 ** 6) 是可以接受的
然后看看这400个整点有无circles内记录的圆心即可
若有说明，这个toy是有机会被包含的

ac code

class Solution:
    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:
        # |o1o2| <= r1 - r2
        # 数据范围的敏感度
        ans = 0
        s = set()
        for x, y in circles:
            s.add((x, y))
        
        for x, y, r1 in toys:
            flag = 0
            # impossible
            if r1 > r:
                continue
            # 两个圆心间隔的最大距离
            # delta < 10
            delta = r - r1
            for i in range(2 * delta + 1):
                for j in range(2 * delta + 1):
                    # 相对位置
                    # 遍历可能的满足的整点(cx, cy)
                    cx, cy = i - delta, j - delta
                    if cx * cx + cy * cy <= delta * delta:
                        # 看看这个范围内有无circles的圆心
                        if (x + cx, y + cy) in s:
                            flag = 1
                            break
                if flag:
                    break
            ans += flag



             
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

总结

几何圆的关系判断
数据范围的特定优化解法