Editorial for CCC '18 S1 - Voronoi Villages

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.

Author: Kirito

Observe that the boundaries of a neighbourhood are defined by the two adjacent villages. Thus we can sort the villages, and then compute the midpoint of each adjacent pair of villages to obtain the neighbourhood boundaries. Finally, iterate over all the boundaries and compute the size of each neighbourhood, and output size of the smallest one.

Note that in certain languages, large floating point numbers may sometimes be printed in scientific notation.

Time Complexity: $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~

Comments

14

ypaula521 commented on Dec. 23, 2019, 2:41 p.m.

This might be really random, but why would you go through the fuss of finding the midpoint, storing them, and then iterating over the boundaries when you could just take the difference between any two neighbourhoods and then dividing by 2? (And then doing that on either side of a neighbourhood?)