Стримування Зомбі
Поняття критичної маси зомбі пов'язане з апокаліпсисом: коли кількість зомбі перевищує певний поріг 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 множини, буде вважатися коректною.