#C8347. Drone Communication Network

    ID: 52319 Type: Default 1000ms 256MiB

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