eolymp
bolt
Try our new interface for solving problems
Məsələlər

Тараканы

Тараканы

Zaman məhdudiyyəti 0.3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Каждую полночь в квартире ученого Васи начинается ужас. Сотни..., о нет! ТЫСЯЧИ тараканов вылазят из каждой дырки к его обеденному столу, уничтожая все крошки и объедки! Вася ненавидит тараканов. Он очень долго думал и сделал Супер-ловушку, которая привлекает всех тараканов в большой зоне после активации. Он планирует активировать ловушку сегодня ночью. Но есть проблема. Эта очень эффективная ловушка с её очень большой зоной работы поглощает огромное количество энергии. Так что, Вася планирует минимизировать время работы этой ловушки. Он собрал информацию о всех местах, в которых живут тараканы. Также он заметил, что все тараканы двигаются только по линиям его скатерти с постоянной скоростью (мы можем предположить, что эта скорость равна 1, так что таракан расположенный в одной из секций, может за 1 единицу времени переместится на любую соседнюю секцию (по вертикали или горизонтали)). Вася решил активировать его ловушку в одной из секций. Когда ловушка активирована, все тараканы будут двигаться к секции, содержащей ловушку, так быстро, как только смогут. Поэтому в любой момент времени после активации тараканы двигаются к секции, в которой находится ловушка, максимально уменьшая расстояние до неё. Если есть два пути с одинаковым расстоянием, то таракан выберет любой. Напишите программу для Васи, которая выбирает секцию, минимизирующую время, необходимое для уничтожения всех тараканов. Конечно, ваша программа будет считать, что скатерть будет плоскостью с декартовой системой координат и секции - точки с целыми координатами.

Giriş verilənləri

В первой строке содержится число мест n (1 n 10000), в которых живут тараканы. Следующие n строк содержат x и y - координаты мест, в которых живут тараканы (целые числа не больше по абсолютному значению).

Çıxış verilənləri

Вам необходимо вывести только два целых числа x и y - координаты секции, которая минимизирует время работы. Если существует более одного решения, то выведите любое из них.

Nümunə

Giriş verilənləri #1
2
1 1
3 3
Çıxış verilənləri #1
2 2
Mənbə 2012 Харьков, Зимняя школа, День Сергея Копеловича, Задача P