Find Maximum Chain Activations

You are given n devices, where each device is represented as [x, y, r]. Device i is located at coordinates (x, y) and can directly activate device j if the Euclidean distance between them is less than or equal to r_i.

Activation is directional: device i may be able to activate device j even when j cannot activate i.

If you manually activate exactly one device first, every device reachable from it, directly or indirectly, will also become activated.

Return the maximum number of devices that can be activated by choosing the best starting device.

Also explain the time and space complexity of your approach.

Find Maximum Chain Activations

Constraints

• 0 <= n <= 100, where n is the number of devices
• -10^5 <= x_i, y_i <= 10^5
• 0 <= r_i <= 10^5
• All coordinates and radii are integers

Examples

Example 1

Input: ([[2, 1, 3], [6, 1, 4]],)
Output: 2

Explanation: Device 1 can activate device 0 because the distance is 4 and its radius is 4. Starting from device 1 activates both devices.

Example 2

Input: ([[0, 0, 2], [2, 0, 2], [4, 0, 2], [10, 0, 1]],)
Output: 3

Explanation: Starting from device 0 activates device 1, which then activates device 2. Device 3 is too far from all others.

Hints

1. Model the devices as a directed graph: add an edge from i to j if device i can activate device j.
2. To test whether one device can activate another, compare squared distances instead of using square roots.