Рассмотрим проекцию на ось x (координата y не влияет на расстояние по x, т.к. все дороги параллельны осям координат). Возьмем два крайних города (с наибольшей и наименьшей координатой). Если бы были только два этих города, то столицу можно было бы расположить в любой точке, между этими городами - суммарное расстояние до них равно расстоянию между городами. Если же столицу расположить вне отрезка, ограниченного двумя крайними городами, то суммарное расстояние будет больше расстояния между городами, а этого нам не надо. Теперь рассмотрим пару предпоследних городов: для нее также должно выполняться это условие. Точно также оно должно выполняться для всех пар городов. Получается, что координата столицы по x должна лежать в отрезке между двумя средними городами (если городов нечетное количество, то столица должна быть в окрестностях среднего города). Т.е. нужно отсортировать координаты по x и выбрать за координату столицы средний элемент. Точно также нужно поступить и с y проекцией. Мы знаем приблизительные координаты столицы (средние элементы отсортированных массив координат городов), попытаемся получить ее точные координаты. В клетке, которую мы выбрали, может находиться другой город, а столицу надо построить на свободном месте, так что этот вопрос надо как-то решать. Это проблема решается небольшим перебором в окрестности этой точки, которая имеет заведомо большую площадь, чем могут занимать все города вместе взятые. Я использовал квадрат со стороной 23 и центром в точке с приблизительными координатами столицы. Мы должны перебрать все точки в этой окрестности и, если в некоторой точке нет города, посчитать сумму расстояний от нее до всех городов и выбрать среди всех точек такую, сумма расстояний для которой будет наименьший.
Задана таблица, некоторые клетки содержат города. Расстояние между городами определяется как |x1 - x2| + |y1 - y2|. Требуется выбрать место для столицы так, чтобы суммарное расстояние до всех городов было минимальным. Столица не должна совпадать с существующим городом.
В некотором царстве, в некотором государстве было \(N\) городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |\(x_1\) - \(x_2\)| + |\(y_1\) - \(y_2\)|.
Император решил построить \(N\)+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.
Нелегкая задача выбрать место для столицы поручена Вам.
Входные данные
В первой строке вводится число \(N\) - количество городов (1 <= \(N\) <= 100). Следующие \(N\) строк содержат координаты городов - пары целых чисел, не превышающих 1000 по абсолютной величине.
Выходные данные
Выведите два целых числа - координаты точки, где следует построить столицу. Если решений несколько, выведите любое.