"""
iteration + sorting + binary search
T: O(n+Cm)
S: O(1)
if circle j can hoop the toyi,
then toyi is Inclusion, inscribed or totally overlapping with cicle j
xj.e., 0 <= d <= r - ri
since 1 <= r, ri <= 10
then d <= 10-1=9
since d is integer, then d is in range [0, 9]
we can iterates all possble centers of circle for each toy
"""
class Solution:
def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:
def check(xi: int, yi: int, ri: int) -> bool:
"""
whether ith toy can be hooped by any circle
"""
d = r-ri
if d < 0:
return False
left, right = xi-d, xi+d
down, up = yi-d, yi+d
for xj in range(left, right+1):
if not yjs[xj]:
continue
a = bisect_left(yjs[xj], down)
b = bisect_right(yjs[xj], up)
for idx in range(a, b):
yj = yjs[xj][idx]
if (xj-xi)**2 + (yj-yi)**2 <= d**2:
return True
return False
m, n = len(toys), len(circles)
# 1. O(nlogn) sort circles array by xj and yj
circles.sort()
# 2. O(n) store yjs of each xj in circles array
yjs = defaultdict(list)
for xj, yj in circles:
yjs[xj].append(yj)
# 3. O(m) iterates over toys array
ans = sum(check(*toy) for toy in toys)
return ans
class Solution:
def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:
def check(xi: int, yi: int, ri: int) -> bool:
# 检查是否可以将第i个玩具套圈
d = r-ri
if d < 0:
return False
left, right = xi-d, xi+d
down, up = yi-d, yi+d
for xj in range(left, right+1):
if not yjs[xj]:
continue
a = bisect_left(yjs[xj], down)
b = bisect_right(yjs[xj], up)
for idx in range(a, b):
yj = yjs[xj][idx]
if (xj-xi)**2 + (yj-yi)**2 <= d**2:
return True
return False
m, n = len(toys), len(circles)
circles.sort() # 按x坐标排序圈的数组
yjs = defaultdict(list) # 为每个x坐标存储y坐标的列表
for xj, yj in circles:
yjs[xj].append(yj)
ans = sum(check(*toy) for toy in toys) # 对所有玩具应用check函数并计数
return ans