Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Вложенный вложенный тернарный поиск: Космические спасатели

В галактике находится n планет, на каждой из которых обитают множество различных живых существ. И каждое из них может оказаться в беде! Космические спасатели прекрасно знают об этом и всегда готовы помочь каждому, кому эта помощь действительно понадобится. Стоит только позвать.
 
Сейчас космические спасатели планируют построить самую большую в истории галактики спасательную базу, однако месторасположение будущей базы пока еще не определено. Поскольку помощь иногда требуется абсолютно неотложно, спасатели стремятся найти такую точку в галактике, из которой можно было бы добраться до самой удаленной планеты за наименьшее возможное время. Другими словами, необходимо найти такую точку в пространстве, чтобы расстояние от нее до самой удаленной от нее планеты было наименьшим из всех возможных точек в пространстве. К сожалению, они не в силах решить такую задачу.
 
Поскольку планеты достаточно удалены друг от друга, их можно считать точками в евклидовом трехмерном пространстве. Расстояние между точками (xi, yi, zi) и (xj, yj, zj) вычисляется по формуле:
Спасательная база может располагаться в любой точке пространства, в том числе, совпадать с какой либо из планет.
 
Галактика в опасности! Спасите космических спасателей и укажите им искомую точку.
 
Входные данные
В первой строке входного файла содержится целое число n — количество планет (1 ≤ N ≤ 100). Каждая из последующих n строк содержит информация о планетах. i-я из этих строк содержит три целых числа xi, yi, zi — координаты i-й планеты ( - 104 ≤ xi, yi, zi ≤ 104, 1 ≤ i ≤ n). Никакие две планеты не совпадают.
 
Выходные данные
В первой строке выходного файла следует вывести три вещественных числа через пробел x0, y0, z0 — координаты будущей базы. Если существует несколько решений, то разрешается вывести любое. Ответ будет засчитан, если расстояние от данной точки до самой удаленной планеты будет отличаться от результата жюри не более чем на 10-6 по абсолютному или относительному значению.
 
Ввод Вывод
5
5 0 0
-5 0 0
0 3 4
4 -3 0
2 2 -2
0.000 0.000 0.000

Источник: http://codeforces.com/contest/106/problem/E


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: