eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сдерживание Зомби

Сдерживание Зомби

\includegraphics{https://static.e-olymp.com/content/d6/d64b5f00cc3b67ba2a12ec568dbfbdf21c849cd3.jpg} С апокалипсисом зомби связано понятие критической массы зомби: когда их количество превысит некоторое пороговое значение \textbf{T}, все будет потеряно. Ваш город находится в тяжелом положении: его текущее население \textbf{3T}. Вы подозреваете, что кто-то в городе может быть инфицирован, хотя у Вас нет понятия, кто это может быть. Когда симптомы проявятся, для человека уже будет слишком поздно, а также для всех остальных в городе, которые были инфицированы этим человеком. Чтобы предотвратить возможность достижения критической массы, Вы собираетесь разделить город на \textbf{3} региона с помощью множества стен. Город имеет треугольный вид, и поэтому Вы собираетесь разделить его на \textbf{3} меньших треугольника, выбрав одну точку разделения и возведя ровные стены между этой точкой и тремя вершинами внешней стены. Это необходимо сделать немедленно, нет времени на переезд людей. Можете ли Вы найти такую точку, что каждый из трех регионов будет содержать в точности \textbf{T }людей? \InputFile Состоит из нескольких тестов. Каждый тест имеет следующую структуру: \begin{itemize} \item Строка \textbf{1}: целое число \textbf{n} (\textbf{3} ≤ \textbf{n} ≤ \textbf{30000}) указывает на количество людей, \textbf{n }всегда кратно \textbf{3}. \item Строки от \textbf{2 }до \textbf{4}: два числа \textbf{x_i} и \textbf{y_i} (\textbf{-10 }≤ \textbf{x_i}, \textbf{y_i} ≤\textbf{ 10}) - координаты \textbf{i}-го угла города. Углы города заданы в порядке обхода против часовой стрелки. \item Строки от \textbf{5 }до \textbf{n + 4}: два числа \textbf{x_i} и \textbf{y_i} (\textbf{-10 }≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{10}) - координаты \textbf{i}-го человека. Все люди находятся строго внутри города-треугольника. \end{itemize} Последняя строка содержит \textbf{0} и не обрабатывается. Никакие два человека не будут коллинеарны ни с одной из вершин города - треугольника. Гарантируется, что для любых людей \textbf{I }и \textbf{J }и любого угла \textbf{A }угол \textbf{IAJ }будет как минимум \textbf{10^\{-7\}} радиан. \OutputFile Для каждого теста вывести строку с двумя числами \textbf{x }и \textbf{y} - координатами точки разделения города. Каждый человек должен находиться строго внутри одной из трех образовавшихся треугольных областей. Каждого человека считайте точкой с нулевым радиусом, а стену - прямой с нулевой толщиной. Гарантируется, что точка разделения существует; причем если эту точку подвинуть на \textbf{10^\{-7\}} в любом направлении, то она все еще будет оставаться точкой разделения. Любая точка, разделяющая людей на \textbf{3 }множества, будет считаться корректной.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
3
0.0 0.0
10.0 0.0
0.0 10.0
4.0 4.0
1.0 4.0
4.0 1.0
0
Выходные данные #1
3.0 3.0
Источник 2010 ACM North America - Pacific Northwest, Задача B