Автор разбора: Михаил Густокашин

Рассмотрим проекцию на ось x (координата y не влияет на расстояние по x, т.к. все дороги параллельны осям координат). Возьмем два крайних города (с наибольшей и наименьшей координатой). Если бы были только два этих города, то столицу можно было бы расположить в любой точке, между этими городами - суммарное расстояние до них равно расстоянию между городами. Если же столицу расположить вне отрезка, ограниченного двумя крайними городами, то суммарное расстояние будет больше расстояния между городами, а этого нам не надо.
Теперь рассмотрим пару предпоследних городов: для нее также должно выполняться это условие. Точно также оно должно выполняться для всех пар городов. Получается, что координата столицы по x должна лежать в отрезке между двумя средними городами (если городов нечетное количество, то столица должна быть в окрестностях среднего города). Т.е. нужно отсортировать координаты по x и выбрать за координату столицы средний элемент. Точно также нужно поступить и с y проекцией.
Мы знаем приблизительные координаты столицы (средние элементы отсортированных массив координат городов), попытаемся получить ее точные координаты. В клетке, которую мы выбрали, может находиться другой город, а столицу надо построить на свободном месте, так что этот вопрос надо как-то решать.
Это проблема решается небольшим перебором в окрестности этой точки, которая имеет заведомо большую площадь, чем могут занимать все города вместе взятые. Я использовал квадрат со стороной 23 и центром в точке с приблизительными координатами столицы. Мы должны перебрать все точки в этой окрестности и, если в некоторой точке нет города, посчитать сумму расстояний от нее до всех городов и выбрать среди всех точек такую, сумма расстояний для которой будет наименьший.