ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > Неотсортированные > задача:


Макс и фуршет

Гость
• Вопросы к жюри (2)

Задачи раздела

• Макс и словарь синонимов
• Макс и смешивание красок
• Макс и степени двойки
• Макс и судоку
• Макс и техническая литература
• Макс и трекер шагов
• Макс и фильтрация спама
• Макс и формирование команд
• Макс и фуршет
• Макс, поезд и самолёт
• Максимум из трех
• Медиана
• Окраска кубика
• Простейшая задача
• Путёвка и считалка
• Ромб
• Следующее число

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и фуршет
Макс и фуршет
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Макса пригласили на праздничный фуршет. В зале расставлены $$$N$$$ столов с различными закусками; $$$i$$$-й стол расположен в точке с координатами $$$(X_i; Y_i)$$$. Макс хочет попробовать все виды закусок, но ему вряд ли удастся унести по угощению с каждого стола одновременно.

Поэтому Макс придумал более хитрый план:

  1. В соседнем помещении есть свободные столы. Макс возьмёт один из них и поставит его в зал;
  2. Затем Макс по одному разу сходит от добавленного стола ко всем остальным столам и соберёт на новом столе все виды закусок;
  3. Наконец, довольный Макс будет занят поеданием угощений.

Конечно же, Макс не хочет слишком много ходить по залу, поэтому ему нужно выбрать место для нового стола так, чтобы сумма расстояний от него до всех остальных столов оказалась как можно меньше. Возможно, наилучшее место совпадёт с одним из имеющихся столов, и тогда Максу не придётся приносить новый.

Помогите Максу определить, где следует разместить стол.

Входные данные

Первая строка содержит целое число $$$N$$$ ($$$1 \le N \le 100$$$) — количество столов с закусками.

Следующие $$$N$$$ строк описывают столы. Каждая из них содержит целые числа $$$X_i$$$ и $$$Y_i$$$ ($$$-1000 \le X_i, Y_i \le 1000$$$) — координаты стола. Координаты всех столов различны.

Выходные данные

Выведите два вещественных числа — координаты точки, в которой Макс должен разместить собственный стол (эта точка может совпадать с расположением одного из имеющихся столов). Если подходящих ответов несколько, выведите любой из них.

Ваш ответ будет считаться верным, если сумма расстояний от выведенной точки до всех столов будет отличаться от минимальной не более, чем на $$$10^{-4}$$$ (по абсолютной или относительной величине).

Примеры

Входные данные
4
0 0
0 10
10 10
10 0
Выходные данные
5.000000000 5.000000000
Входные данные
5
3 -1
4 2
1 6
-4 -1
-2 4
Выходные данные
0.649681630 2.373452207

Для отправки решений необходимо выполнить вход.

www.contester.ru