Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Overlapping Disks by kdim
def overlapping_disks(disks: list[tuple[int, int, int]]) -> int:
events = [] # x-coordinate, Side, Disk
for x, y, r in disks:
events.append((x - r, 0, (x, y, r))) # 0 - Left
events.append((x + r, 1, (x, y, r))) # 1 - Right
events.sort(key=lambda e: e[:2])
active, count = set(), 0
for _, event, (x1, y1, r1) in events:
if not event: # Left event
for x2, y2, r2 in active:
if (x2 - x1) ** 2 + (y2 - y1) ** 2 <= (r1 + r2) ** 2:
count += 1 # Intersect
active.add((x1, y1, r1))
else: # Right Event
active.remove((x1, y1, r1))
return count
Nov. 19, 2024
