Симметрия 2
Симметрия 2
Отражением точки 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
в противном случае.
Пример
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