Gegeben eine Liste von disks auf der zweidimensionalen Ebene, dargestellt als Tupel (x, y, r) so dass x, y der Mittelpunkt und r der Radius dieser Scheibe ist, zählen Sie, wie viele Paare von Scheiben sich schneiden.

Zwei Scheiben (x1, y1, r1) und (x2, y2, r2) schneiden sich nur dann, wenn sie die pythagoreische Ungleichung (x2-x1)**2+(y2-y1)**2<=(r1+r2)**2 erfüllen.

Beachten Sie, dass diese präzise Formel mit reiner Ganzzahlarithmetik arbeitet, wenn ihre Argumente ganzzahlig sind. Es gibt also keine Quadratwurzeln oder andere irrationale Zahlen, die die Arbeit mit all dem dezimalen Rauschen vermasseln. (Diese Formel verwendet auch den Operator <=, um zwei sich küssende Scheiben als ein sich überschneidendes Paar zu zählen).

Bei diesem Problem würde eine grobe Schleifenbildung durch alle möglichen Scheibenpaare zwar funktionieren, aber bei großen Listen schrecklich ineffizient werden. Ein sweep line algorithm kann dieses Problem jedoch nicht nur effektiv, sondern auch effizient lösen (ein entscheidender, aber oft übersehener Unterschied), indem es weit weniger Scheibenpaare betrachtet.

Hier ist ein Schema für [(0, 0, 3), (6, 0, 3), (6, 6, 3), (0, 6, 3)]:

Eingabe: Liste (List) von Tupeln (tuple) von ganzen Zahlen (int).

Ausgabe: Ganzzahl (int).

Beispiele:

assert overlapping_disks([(0, 0, 3), (6, 0, 3), (6, 6, 3), (0, 6, 3)]) == 4
assert overlapping_disks([(4, -1, 3), (-3, 3, 2), (-3, 4, 2), (3, 1, 4)]) == 2
assert (
    overlapping_disks([(-10, 6, 2), (6, -4, 5), (6, 3, 5), (-9, -8, 1), (1, -5, 3)])
...