Editorial for CCC '18 S1 - Voronoi Villages
Submitting an official solution before solving the problem yourself is a bannable offence.
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)~