Question

def count_overlapping_disks(disks):

Right on the heels of the previous Manhattan skyline problem, another classic problem of similar spirit that is here best solved with a sweepline 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, including the edge, have at least one point in common. To test whether two disks (x1, y1, r1) and (x2, y2, r2) intersect, use the Pythagorean formula (x2-x1)**2 + (y2-y1)**2 <= (r1+r2)**2. (Note again how this precise formula uses only integer arithmetic whenever all individual components are integers. And no square roots or some other nasty irrational numbers.)

For this problem, crudely looping through all possible pairs of disks would be horrendously inefficient as the list grows larger. However, a sweepline 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 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 between that disk and only the disks presently in the active set.

disks	Expected result
[(0, 0, 3), (6, 0, 3), (6, 6, 3), (0, 6, 3)]	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), (1, -5, 3)]	2
[(x, x, x // 2) for x in range(2, 101)]	2563

Answer 1

# Thank you for asking the question.

def count_overlapping_disks(disks):
count=0
for i in range(len(l)-1):
for j in range(i+1,len(l)):
distSq = (l[i][0] - l[j][0]) * (l[i][0] - l[j][0]) + (l[i][1] - l[j][1]) * (l[i][1] - l[j][1]);
radSumSq = (l[i][2] + l[j][2]) * (l[i][2] + l[j][2]);
if (distSq <= radSumSq):
count+=1
return count
# Driver code
l=[]
for a in range(2,101):
l.append((a,a,a//2))
t = count_overlapping_disks(l)
print(t) # output will be 2563

# Kindly check indentation because indentation gets change after submitting the question.

# Hope this will help you.

# Feel free to ask any doubt and once again thank you very much.