Overlapping Circle Groups
MediumGeometry · Intuit
Each circle is [x, y, r]: centre (x, y) and radius r, all integers.
Two circles are directly connected if they overlap or touch, that is, if the distance between their centres is at most r1 + r2. This includes one circle lying entirely inside another. Connection is transitive: if circle A is connected to B and B to C, then A, B and C are all in the same group even if A and C do not overlap.
Return the number of groups.
Example 1
- Input:
- circles = [[0, 0, 2], [3, 0, 2], [10, 0, 1]]
- Output:
- 2
- Explanation
- The first two centres are 3 apart and their radii sum to 4, so the circles overlap and form one group. The third circle is 7 away from the second, more than 2 + 1, so it forms its own group.
Example 2
- Input:
- circles = [[0, 0, 1], [3, 0, 2], [3, 4, 2], [20, 20, 1]]
- Output:
- 2
- Explanation
- Circles 0 and 1 are exactly 3 apart with radii summing to 3, so they touch, which counts. Circle 2 is 4 above circle 1 with radii summing to 4, so it touches circle 1 too. Circles 0 and 2 are 5 apart and never meet, but they share a group through circle 1. Circle 3 is far from everything, so there are 2 groups.
Example 3
- Input:
- circles = [[0, 0, 5], [0, 0, 1]]
- Output:
- 1
- Explanation
- The small circle lies entirely inside the big one. They share area, so they overlap and form a single group.
Constraints
0 <= circles.length <= 1000-10^9 <= x, y <= 10^91 <= r <= 10^9