Зайняті бджоли#4322
Є нескінченний вулик, який складається з шестикутних комірок. У деяких комірках знаходяться робітники, які доставляють мед королеві. У довільний момент часу довільна комірка може містити довільну кількість бджіл. Робітники можуть пересуватись лише між сусідніми (що мають спільну сторону) комірками, королева пересуватись не може. Відстань між двома комірками дорівнює найменшій кількості кроків, за які робітник може потрапити з однієї комірки в іншу. Робітники дуже зайняті, тому вони хочуть витратити найменший час на шляху до королеви.
Вам задано координати різних комірок, у яких знаходяться робітники; система координат подана нижче. Знайдіть таке розміщення королеви, щоб сумарна відстань, пройдена робітниками зі своїх комірок до неї, була мінімальною.
Перший рядок містить кількість робітників (1 \leq N \leq 10^5). Кожен з наступних рядків містить два цілих числа: координати комірок робітників. Значення координат по модулю не перевищують 10^9. Гарантується, що усі комірки різні.
Виведіть координати потрібної комірки. Якщо розв'язків декілька, то виведіть довільний з них.
Приклад 1