Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Overlapping Disks by freeman_lex
# Import necessary modules
from itertools import combinations, product
# Define a function to count the number of overlapping disks
def overlapping_disks(disks: list[tuple[int, int, int]]) -> int:
# Define a helper function to check if two disks overlap
def inter(d1: tuple[int, int, int], d2: tuple[int, int, int]) -> bool:
# Unpack circle coordinates and radiuses
(x1, y1, r1), (x2, y2, r2) = d1, d2
# Check if the squared distance between centers is less than or equal to the squared sum of radiuses
return (x2 - x1) ** 2 + (y2 - y1) ** 2 <= (r1 + r2) ** 2
# Create a sorted list of unique x-coordinates for circle left edges
sweep_range = sorted(set(d[0] - d[2] for d in disks))
# Initialize a set to keep track of active disks
active = set()
# Convert the input list of disks to a set for efficient removal
disks = set(disks)
# Initialize a variable to count overlapping pairs
res = 0
# Iterate through the sweep_range (sorted x-coordinates)
for sw in sweep_range:
# Remove inactive disks that do not intersect the current sweep line
active = set(d for d in active if d[0] + d[2] >= sw)
# Find new disks that intersect the current sweep line
new = set(d for d in disks if d[0] - d[2] == sw)
# Remove new disks from the set of all disks
disks -= new
# Check for intersections between active disks and new disks
for d1, d2 in product(active, new):
res += inter(d1, d2)
# Check for intersections between new disks
for d1, d2 in combinations(new, 2):
res += inter(d1, d2)
# Add new disks to the set of active disks
active |= new
# Return the total count of overlapping pairs
return res
Sept. 16, 2023
Comments:
