python3 解法, 执行用时: 4160 ms, 内存消耗: 22.8 MB, 提交时间: 2023-07-01 13:55:49

class Solution:
    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:
        ans = 0
        v = set((x,y) for x,y in circles)
        for x,y,z in toys:
            if z > r:
                continue
            dis = r - z
            # 若当前玩具可以获得,则一定存在一个圈使其圆心到当前玩具圆心的距离小于dis
            # 枚举圆心
            tag = 0
            for cx in range(x - dis,x + dis + 1):
                for cy in range(y - dis,y + dis + 1):
                    if (cx - x) ** 2 + (cy - y) ** 2 > dis ** 2:
                        continue
                    else:
                        if (cx,cy) in v:
                            tag = 1
                            break
                if tag:
                    break
            if tag:
                ans += 1
        return ans

python3 解法, 执行用时: 584 ms, 内存消耗: 23.1 MB, 提交时间: 2023-07-01 13:55:26

class Solution:
    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:
        circles.sort()
        m = len(circles)
        res = 0
        for xi, yi, ri in toys:
            if ri > r:
                continue
            i = bisect.bisect_left(circles, [xi + ri - r, float('-inf')])
            while i < m:
                x, y = circles[i]
                if x > xi + r - ri:
                    break
                j = bisect.bisect_left(circles, [x, yi])
                if j and (circles[j - 1][0] - xi) ** 2 + (circles[j - 1][1] - yi) ** 2 <= (r - ri) ** 2:
                    res += 1
                    break
                if j < m and (circles[j][0] - xi) ** 2 + (circles[j][1] - yi) ** 2 <= (r - ri) ** 2:
                    res += 1
                    break
                i = bisect.bisect_left(circles, [x, float('inf')])
        return res

python3 解法, 执行用时: 1116 ms, 内存消耗: 22.8 MB, 提交时间: 2023-07-01 13:55:02

class Solution:
    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:

        cirs = set()
        for x,y in circles: #所有套圈的圆心进哈希集合
            cirs.add((x,y))

        def check(tx,ty,dif):
            for cx in range(tx-dif,tx+dif+1):
                for cy in range(ty-dif,ty+dif+1):
                    #注意由于圆形区难以枚举，实际枚举的是该圆形区外切的正方形区，要判断一下是否真的是圆心距小于半径差
                    if (cx-tx)*(cx-tx)+(cy-ty)*(cy-ty)<=dif*dif and (cx,cy) in cirs:
                        return True
            return False
        
        ans = 0
        for tx,ty,tr in toys:
            ans+=check(tx,ty,r-tr) #如果套圈比玩具小，check函数根本不会循环，直接就False了，无需特判
        return ans

cpp 解法, 执行用时: 1896 ms, 内存消耗: 107.2 MB, 提交时间: 2023-07-01 13:54:25

class Solution {
    using ll = long long;
public:
    ll change(ll x, ll y) {
        // 将坐标映射到 long long 型的整数
        return x * 1000000000 + y;
    }
    
    int circleGame(vector<vector<int>>& toys, vector<vector<int>>& circles, int r) {
        unordered_map<ll, int> d;
        unordered_set<ll> s;
        
        // 保存所有玩具的圆心坐标
        for(auto &t : toys) s.insert(change(t[0], t[1]));
        
        for(auto &c : circles) {
            int x = c[0], y = c[1];
            
            // 遍历内部所有点
            for(int j = x - r; j <= x; ++j) {
                for(int k = y; k >= y - r; --k) {
                    // 剪枝 ： 若当前点不在套圈内部，直接 break
                    ll now = r - sqrt((x - j) * (x - j) + (y - k) * (y - k));
                    if(now < 0) break;
                    int ans = now;
                    
                    // 如果某个点是某个玩具的圆心，我们才进行更新
                    ll a = change(j, k), b = change(2 * x - j, k), c = change(j, 2 * y - k), e = change(2 * x - j, 2 * y - k);
                    if(s.count(a)) d[a] = max(ans, d[a]);
                    if(s.count(b)) d[b] = max(ans, d[b]);
                    if(s.count(c)) d[c] = max(ans, d[c]);
                    if(s.count(e)) d[e] = max(ans, d[e]);
                }
            }
        }
        
        ll ret = 0;
        for(auto &t : toys) {
            // 该玩具半径小于等于其最大可能被覆盖半径，说明会被套圈套住
            if(d[change(t[0], t[1])] >= t[2]) ret++;
        }
        
        return ret;
    }
};

golang 解法, 执行用时: 192 ms, 内存消耗: 7.7 MB, 提交时间: 2023-07-01 13:53:38

func circleGame(toys [][]int, circles [][]int, r0 int) (ans int) {
	sort.Slice(circles, func(i, j int) bool { a, b := circles[i], circles[j]; return a[0] < b[0] || a[0] == b[0] && a[1] < b[1] })

	// 将横坐标相同的圈分为一组
	type pair struct{ x int; ys []int }
	a, y := []pair{}, -1
	for _, p := range circles {
		if len(a) == 0 || p[0] > a[len(a)-1].x {
			a = append(a, pair{p[0], []int{p[1]}})
			y = -1
		} else if p[1] > y { // 去重
			a[len(a)-1].ys = append(a[len(a)-1].ys, p[1])
			y = p[1]
		}
	}

	for _, t := range toys {
		x, y, r := t[0], t[1], t[2]
		if r > r0 {
			continue
		}
		i := sort.Search(len(a), func(i int) bool { return a[i].x+r0 >= x+r })
		for ; i < len(a) && a[i].x-r0 <= x-r; i++ {
			cx, ys := a[i].x, a[i].ys
			j := sort.SearchInts(ys, y)
			if j < len(ys) {
				if cy := ys[j]; (x-cx)*(x-cx)+(y-cy)*(y-cy) <= (r0-r)*(r0-r) {
					ans++
					break
				}
			}
			if j > 0 {
				if cy := ys[j-1]; (x-cx)*(x-cx)+(y-cy)*(y-cy) <= (r0-r)*(r0-r) {
					ans++
					break
				}
			}
		}
	}
	return
}