Count overlapping disks def count_overlapping_disks(disks): Right on the heels of the previous Manhattan skyline problem, here is another classic of similar spirit for us to solve efficiently with a sweep line algorithm. Given a list of disks on the two- dimensional plane as tuples (x,y,r) so that (x,y) is the center point and r is the radius of that disk, count how many pairs of disks intersect each other in that their areas have at least one point in common. To test whether disks (x1,yl,rl) and (x2,y2,r2) intersect, use the Pythagorean formula (x2-x1)**2+(y2-yl)**2<=(rl+r2)**2. Note again how this precise formula needs only integer arithmetic whenever the individual components are integers, with no square roots or any other irrational numbers gumming up the works with their infinite chaos of decimals that we can only approximate by never complete. For this problem, crudely looping through all possible pairs of disks would work but be horrendously inefficient as the list grows larger. However, a sweep line algorithm can solve this problem by looking at a far fewer pairs of disks. Again, sweep through the space from left to right for all relevant x-coordinate values and maintain the set of active disks at the moment. Each individual disk (x,y,r) enters the active set when the vertical sweep line reaches the x-coordinate x-r, and leaves the active set when the sweep line reaches x+r. When a disk enters the active set, check for an intersection only between that disk and the disks in the active set. Expected result disks 1(0, о, 3), (6, о, 3), (6, 6, 3), (о, 6, 3)1 4 [(4, -1, 3), (-3, 3, 2), (-3, 4, 2), (3, 1, 4)] 2 [(-10, 6, 2), (6, -4, 5), (6, 3, 5), (-9, -8, 1), 2 (1, -5, 3)] [(x, x, x // 2) for x in range (2, 101)] 2563