Занятые пчелы
Имеется бесконечное количество улей, состоящих из шестиугольных ячеек. В некоторых клетках находятся работники, доставляющие мед королеве. В произвольный момент времени любая клетка может содержать любое количество пчел. Работники могут передвигаться только между соседними (имеющими общую сторону) ячейками, королева передвигаться не может. Расстояние между двумя ячейками равно наименьшему числу шагов, за которое работник может попасть из одной ячейки в другую. Работники очень заняты, поэтому они хотят потратить наименьшее время на пути к королеве.
Вам заданы координаты N различных ячеек, в которых находятся работники; система координат представлена ниже. Найдите такое расположение королевы, чтобы суммарное расстояние пройденное работниками со своих ячеек к ней было минимальным.
Входные данные
Первая строка содержит количество работников N (1 ≤ N ≤ 10^5). Каждая из следующих N строк содержит два целых числа: координаты ячеек работников. Значения координат по модулю не превосходят 10^9. Гарантируется, что все ячейки различны.
Выходные данные
Вывести координаты требуемой ячейки. Если решений несколько, то вывести любое из них.