#P3416. Moo-cast Broadcast
Moo-cast Broadcast
Moo-cast Broadcast
Farmer John's $N$ cows ($1 \leq N \leq 200$) are setting up an emergency "moo-cast" system to broadcast messages among themselves. Each cow is equipped with a walkie-talkie that has a limited transmission power. A walkie-talkie with power $P$ can only transmit to cows within a distance of $P$ (note that transmission is not necessarily bidirectional).
Cows can relay messages along a series of hops. Determine the maximum number of cows that can be reached by a broadcast originating from a single cow.
Input Format: The first line contains an integer $N$. The next $N$ lines each contain three integers $x_i$, $y_i$, and $P_i$, representing the coordinates and the transmission power of the i-th cow.
Note: A cow A can transmit to cow B if and only if $$ (x_A-x_B)^2+(y_A-y_B)^2 \leq P_A^2. $$
Output Format: Output a single integer representing the maximum number of cows that can be reached by a broadcast, including the originating cow.
inputFormat
The first line contains a single integer $N$, the number of cows. Each of the next $N$ lines contains three space-separated integers: $x_i$, $y_i$, and $P_i$.
outputFormat
Output a single integer, the maximum number of cows that can be reached through the broadcast from one starting cow.
sample
4
1 3 5
5 4 3
7 2 1
6 1 1
3