Задачка про города

[venco]

Минимальный круг проходит либо через город слева по дороге, либо через город справа, либо через оба (город ровно напротив станции будем считать находящимся и слева, и справа).
Если минимальный круг проходит через город слева (или напротив), то при смещении станции направо круг обязательно увеличится, так как он должен продолжать охватывать этот город на границе, а расстояние до него увеличится. При этом города, находящиеся справа, строго приблизятся, т.е. не смогут оказаться на границе, пока они справа. Таким образом, если в каком-то положении станции граница минимального круга проходит через город слева (напротив), то во всех положениях станции правее граница также будет определятся городами слева, а значит, так и будет увеличиваться.
Аналогично, если круг проходит через город справа (напротив), то при смещении станции налево во-первых, минимальный круг увеличится, во-вторых, так и будет продолжатся увеличиваться при дальнейшем смещении станции налево.
Таким образом, минимум строго один, и достигается в таком положении станции, что либо граница проходит через два города по разные стороны в направлении дороги, либо через город строго напротив станции.

[Cave]

Извините, я дальше не читал, сразу не понял, что такое города слева и справа по дороге. Поясните, пожалуйста.

[venco]

Если координаты станции - $(x_s,0)$, то "слева" - это все точки с координатой $x<x_s$, а "справа" - с координатой $x>x_s$. "Напротив" - с координатой $x=x_s$. Координата $y$ - любая.

[Cave]

Спасибо. Выглядит всё правдоподобно.
Сложность в таком случае получается $O(N\log C)$, где $N$ - число городов, а $C$ - максимум модуля $x$-координат городов.