Організація ігрового майданчика#3365

Організація ігрового майданчика

1 секунда

64 мегабайти

Дуже складна

Ти організовуєш веселий захід на ігровому майданчику! Майданчик має форму трикутника, і на ньому хочуть погратись $3 T$ дітей. Ти хочеш поділити майданчик на $3$ ігрові зони так, щоб у кожній зоні було рівно $T$ дітей.

Майданчик має форму трикутника, і тобі потрібно знайти спеціальну точку всередині нього. З цієї точки ти створиш $3$ зони, проводячи лінії до трьох кутів майданчика. Таким чином майданчик буде поділено на $3$ менших трикутника. Чи можеш ти знайти таку точку, щоб у кожній зоні було рівно $T$ дітей?

Вхідні дані

Кілька тестів. Кожен тест має таку структуру:

Рядок $1$ : ціле число $n$ ( $3 \leq n \leq 30000$ 3 \le n \le 30000) - кількість дітей, $n$ завжди кратне $3$ .
Рядки від $2$ до $4$ : два числа $x_{i}$ x_i і $y_{i}$ y_i ( $- 10 \leq x_{i}, y_{i} \leq 10$ -10 \le x_i, y_i \le 10) - координати $i$ -го кута майданчика. Кути майданчика задані в порядку обходу проти годинникової стрілки.
Рядки від $5$ до $n + 4$ n + 4: два числа $x_{i}$ x_i і $y_{i}$ y_i ( $- 10 \leq x_{i}, y_{i} \leq 10$ -10 \le x_i, y_i \le 10) - координати $i$ -ї дитини. Всі діти знаходяться строго всередині майданчика-трикутника.

Останній рядок містить $0$ і не обробляється.

Жодні двоє дітей не будуть колінеарні з жодним з кутів майданчика-трикутника. Гарантується, що для будь-яких дітей $I$ і $J$ і будь-якого кута $A$ кут $I A J$ буде як мінімум $1 0^{- 7}$ 10^{-7} радіан.

Вихідні дані

Для кожного тесту виведи рядок з двома числами $x$ і $y$ - координатами точки поділу майданчика. Кожна дитина повинна знаходитися строго всередині однієї з трьох утворених трикутних областей. Кожну дитину вважай точкою з нульовим радіусом, а лінію - прямою з нульовою товщиною. Гарантується, що точка поділу існує; причому якщо цю точку посунути на $1 0^{- 7}$ 10^{-7} в будь-якому напрямку, вона все ще залишатиметься точкою поділу. Будь-яка точка, що розділяє дітей на $3$ множини однакового розміру, буде вважатися коректною.

Приклади

Приклад 1