Симетрія 2#251

Симетрія 2

2 секунди

64 мегабайти

Складна

Відображенням точки $p$ відносно прямої $L$ є точка $p^{'}$ p', така що відрізок $p p^{'}$ pp' перпендикулярний до прямої $L$ , і його середина лежить на $L$ . Якщо $p$ лежить на $L$ , то $p^{'} = p$ p' = p.

Нехай задано множину точок на площині. Віссю симетрії називається така пряма, що відображення довільної точки з цієї множини відносно прямої також є точкою цієї множини. У цій задачі вам дано набір точок на площині, і ви повинні визначити, чи існує хоча б одна вісь симетрії для цієї множини.

Оскільки використовуються дійсні числа, вважайте віссю симетрії таку пряму, що для будь-якої точки $p$ множини відстань від її відображення $p^{'}$ p' відносно цієї прямої до якоїсь із точок множини не перевищує $1 0^{- 6}$ 10^{-6}.

Вхідні дані

Вхідний файл містить декілька тестів. Перший рядок містить ціле число $K$ ( $1 \leq K \leq 10$ 1 \le K \le 10) — кількість тестів. Перший рядок кожного тесту містить ціле число $N$ — кількість точок у множині ( $1 \leq N \leq 100000$ 1 \le N \le 100\,000). У кожному з наступних $N$ рядків подано опис однієї точки — два дійсних числа $X$ та $Y$ , відокремлених пробілом, — координати точки на площині ( $- 10000 \leq X, Y \leq 10000$ -10\,000 \le X, Y \le 10\,000). Жодні дві точки одного тесту не співпадають. Гарантується, що сума значень $N$ за всіма тестами не перевищує $200000$ .

Вихідні дані

Для кожного тесту виведіть один рядок: $YES$ , якщо існує хоча б одна вісь симетрії для заданої множини точок, і $NO$ у протилежному випадку.

Приклади

Приклад 1