Editorial for COCI '20 Contest 2 #2 Odašiljači


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

First, let's discuss how to check for some fixed radius r if all antennas can communicate. Two antennas can communicate directly if their distance is at most 2r. We can build a graph over antennas, and add edges for all pairs of antennas that are closer than 2r. Then, we need to check if the graph is connected, which can be done for example with DFS.

The optimal r, that is the minimal r for which the constructed graph is connected, can be found using binary search. For the upper bound, we can put for example 10^9. The complexity is \mathcal O(n^2 \log_2 10^9).


Comments

There are no comments at the moment.