#C8347. Drone Communication Network
Drone Communication Network
Drone Communication Network
You are given ( m ) drones in a three-dimensional space. The position of each drone is represented by its coordinates ( (x, y, z) ). Two drones can communicate directly if the Euclidean distance between them is less than or equal to a given threshold ( d ). The Euclidean distance between two points ( (x_1, y_1, z_1) ) and ( (x_2, y_2, z_2) ) is defined as
[ \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2} ]
A communication network is formed by drones that can communicate directly or indirectly (through other drones). Your task is to determine the number of connected components (i.e. isolated communication networks) among all drones.
Note: Two drones belong to the same network if there exists a sequence of drones connecting them such that each adjacent pair is within the distance threshold ( d ).
inputFormat
The first line contains two numbers: an integer ( m ) (the number of drones) and a number ( d ) (the communication distance threshold). This is followed by ( m ) lines, each containing three integers representing the coordinates ( x ), ( y ), and ( z ) of a drone.
outputFormat
Output a single integer representing the number of connected components in the network of drones.## sample
4 5
0 0 0
3 4 0
7 1 5
2 2 2
2