Сдерживание Зомби
С апокалипсисом зомби связано понятие критической массы зомби: когда их количество превысит некоторое пороговое значение T, все будет потеряно. Ваш город находится в тяжелом положении: его текущее население 3T. Вы подозреваете, что кто-то в городе может быть инфицирован, хотя у Вас нет понятия, кто это может быть. Когда симптомы проявятся, для человека уже будет слишком поздно, а также для всех остальных в городе, которые были инфицированы этим человеком.
Чтобы предотвратить возможность достижения критической массы, Вы собираетесь разделить город на 3 региона с помощью множества стен. Город имеет треугольный вид, и поэтому Вы собираетесь разделить его на 3 меньших треугольника, выбрав одну точку разделения и возведя ровные стены между этой точкой и тремя вершинами внешней стены. Это необходимо сделать немедленно, нет времени на переезд людей. Можете ли Вы найти такую точку, что каждый из трех регионов будет содержать в точности T людей?
Входные данные
Состоит из нескольких тестов. Каждый тест имеет следующую структуру:
Строка 1: целое число n (3 ≤ n ≤ 30000) указывает на количество людей, n всегда кратно 3.
Строки от 2 до 4: два числа x_i и y_i (-10 ≤ x_i, y_i ≤ 10) - координаты i-го угла города. Углы города заданы в порядке обхода против часовой стрелки.
Строки от 5 до n + 4: два числа x_i и y_i (-10 ≤ x_i, y_i ≤ 10) - координаты i-го человека. Все люди находятся строго внутри города-треугольника.
Последняя строка содержит 0 и не обрабатывается.
Никакие два человека не будут коллинеарны ни с одной из вершин города - треугольника. Гарантируется, что для любых людей I и J и любого угла A угол IAJ будет как минимум 10^{-7} радиан.
Выходные данные
Для каждого теста вывести строку с двумя числами x и y - координатами точки разделения города. Каждый человек должен находиться строго внутри одной из трех образовавшихся треугольных областей. Каждого человека считайте точкой с нулевым радиусом, а стену - прямой с нулевой толщиной. Гарантируется, что точка разделения существует; причем если эту точку подвинуть на 10^{-7} в любом направлении, то она все еще будет оставаться точкой разделения. Любая точка, разделяющая людей на 3 множества, будет считаться корректной.