Симетрія 2
Симетрія 2
Відображенням точки p відносно прямої L є точка p^{'} така, що відрізок pp^{'} перпендикулярний до прямої L, і його середина лежить на L. Якщо p лежить на L, то p^{'} = p.
Нехай задано множину точок на площині. Віссю симетрії називається така пряма на ці площині, що відображення довільної точки із заданої множини дає також точку з цієї множини. У даній задачі вам задано набір точок на площині, і ви повинні визначити, чи існує хоча б одна вісь симетрії для цих точок.
У зв'язку з використанням дійсних чисел, вважайте віссю симетрії таку пряму, що відстань від відображення довільної точки відносно цієї прямої до якоїсь з точок множини не перевищує 10^{-6}
.
Вхідні дані
Вхідний файл містить декілька тестів. Перший рядок вхідного файлу містить ціле число K (1 <= K <= 10) - кількість тестів. Перший рядок кожного тесту містить ціле число N - кількість точок у множині (1 <= N <= 100 000). У кожному з наступних N рядків розміщено опис однієї точки - два дійсних числа X та Y, відокремлених пропуском - координати точки на площині (-10 000 <= X, Y <= 10 000). Ніякі дві точки з одного тесту не співпадають. Гарантується, що сума значень N по всім тестам не перевищує 200 000.
Вихідні дані
Для кожного тесту виведіть один рядок YES, якщо існує хоча б одна вісь симетрії для заданої множини точок, і NO у протилежному випадку.
Приклад
3 4 -10 0 10 0 10 10 10 -10 4 -10 0 10 1 10 10.5 10 -10.5 6 -1000 30 -100 20 -10 10 1000 30 100 20 10 10
YES NO YES