favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

# Symmetry 2

Given a point p and a line L on the plane, the reflection of p against L is a point p' such that the segment pp' is perpendicular to L and its middle point is on L. If p is on L, then p' = p.

Given a set of points on the plane, the axis of symmetry is a line on the plane such that the reflection of any point of the set against that line gives a point from this set. In this problem you are given a
set of points on the plane, and you must decide whether there exists at least one axis of symmetry or not.

Because of using real numbers, you may assume that the axis of symmetry is a line L such that for any point of the set p its reflection p' against the line L lies within 10-6 distance of some point of the set.

Input

The input contains several test cases. The first line of each input file contains an integer K (1 <= K <= 10) indicating the number of test cases. The first line of each test case contains an integer N indicating the number of points in the set (1 <= N <= 100 000). Each of the next N lines describes a single point of the set using two real numbers X and Y separated by a single space (-10 000 <= X, Y <= 10 000), these numbers represent the coordinates of the point on the plane. You may assume that no two points of each test case have the same location. It is guaranteed that the total sum of values of N for all test cases does not exceed 200 000.

Output

For each test case output a single line YES if there exists at least one axis of symmetry for the provided set of points, or NO otherwise.

Time limit 2 seconds
Memory limit 64 MiB
Input example #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

Output example #1
YES
NO
YES