e-olymp
Задачи

Симметрия 2

Симметрия 2

prb251

Отражением точки p относительно прямой L является точка p' такая, что отрезок pp' перпендикулярен к прямой L, и его середина лежит на L. Если p лежит на L, то p' = p.

Пусть дано множество точек на плоскости. Осью симметрии называется такая прямая на этой плоскости, что отражение отражение любой точки из заданного множества дает также точку из этого множества. В данной задаче вам дан набор точек на плоскости, и вы должны определить, существует ли хотя бы одна ось симметрии для этих точек.

Ввиду использования вещественных чисел, считайте осью симметрии такую прямую, что расстояние от отражения любой точки относительно этой прямой до какой-то из точек множества не превосходит 10^-6.

Входные данные

Входной файл содержит несколько тестов. Первая строка входного файла содержит целое число K (1 <= K <= 10) - количество тестов. Первая строка каждого теста содержит содержит целое число N - количество точек в множестве (1 <= N <= 100000). На каждой из следующих N строк содержится описание одной точки - два вещественных числа X и Y, разделенные пробелом - координаты точки на плоскости (-10000 <= X, Y <= 10000). Никакие две точки из одного теста не совпадают. Гарантируется, что сумма значений N по всем тестам не превосходит 200000.

Выходные данные

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

Лимит времени 2 секунды
Лимит использования памяти 64 MiB
Входные данные #1
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
Выходные данные #1
YES
NO
YES