Streetlights
Time limit0.5sMemory limit256 MB
Given N integer points, decide whether for every pair (xi,yi), (xj,yj) the two reflected points (xi,yj) and (xj,yi) are also present.
- Level
Medium4 of 10
- Topics
- Hash map, Sorting, Implementation, Math
- Solved
- No attempts yet
Problem
N streetlights are placed on a two-dimensional plane. The position of the i-th streetlight is (xi, yi), and each coordinate is an integer. No two streetlights share the same position.
For two streetlights i and j (i < j), streetlights i and j are said to be balanced if there are streetlights at (xi, yj) and (xj, yi). Determine whether every pair of streetlights is balanced.
Input
The first line gives the number of test cases T.
The first line of each test case gives the number of streetlights N, and the following N lines give the positions xi, yi of the streetlights, separated by spaces.
Output
For each test case, print "BALANCED" on one line if every pair of streetlights is balanced, and "NOT BALANCED" otherwise.
Constraints
- 1 ≤ T ≤ 5
- 2 ≤ N ≤ 200,000
- -10^9 ≤ xi, yi ≤ 10^9