Line Reflection

Posted: 20 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Ninja found ‘N’ points on a 2D plane. The points are given in the form of a “N ✕ 2” size array “POINTS”. Ninja wants to find if there is a line such that it is parallel to the Y-axis and it reflects the given set of points. Your task is to help Ninja in this process.

Input format:
The first line of input contains an integer ‘T’, denoting the number of test cases. 

The first line of each test case contains an integer ‘N’, representing the number of points.

The next ‘N’ lines contain two space separated integers representing coordinates of the given point.
Output format:
For each test case, print a single line containing "true" if there is such a line parallel to the Y-axis that reflects the given set of points else print "false".

The output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 10 ^ 5
-10 ^ 9 <= POINTS[i][0], POINTS[i][1] <= 10 ^ 9

Where 'POINTS[i][0]' represents X-axis coordinates and 'POINTS[i][1]' represents Y-axis coordinates of the ith point.

Time Limit: 1 sec.
Approach 1

The basic approach is to find the appropriate reflection line parallel to the Y-axis. The observation is that the average of X coordinates of the symmetry pair will lie on the reflection line. 

 

For example, consider points ‘P1’ and ‘P2’, the symmetry pairs, and ‘X1’ and ‘X2’ are their respective X coordinates, so point (X1 + X2) / 2 will lie on the reflection line. So we can find this point by finding the minimum and maximum values of the X coordinate of all the points, then take an average of minimum and maximum value.

 

Once we find the reflection line, we have to check if all the symmetry pairs exist or not. The observation is that the reflection line will not change the Y coordinate of a point and its reflection, but the X coordinate of the point and its reflection will be at the same distance from the reflection line.

 

Since the reflection line is parallel to Y-axis, we can find its X coordinate as we discussed above. Let the X coordinate of the reflection line be X. Consider two points [X1, Y1] and [X2, Y2], which reflect each other to the reflection line. So we can say that Y1 = Y2 and X - X1 = X2 - X, which can also be written as (2 * X) - X1 = X2 or (2 * X) - X2 = X1. If these conditions are satisfied, then the two points are symmetry pairs.

 

To find reflection for each point, we can iterate through the array “points” and check if there exists any point that satisfies both the conditions that we discussed above.

 

If we find at least one reflection for each point, print true else print false.

 

Algorithm:

 

  • First, iterate through the array “points” and find the minimum and maximum X coordinates over the array and store them in "minimumX" and "maximumX".
  • Find the X coordinate of the reflection line and store it in variable 'reflectionX'. reflectionX = (minimumX + maximumX) / 2.
  • Now, iterate over the array "points"
    • For each point, consider value [X1, Y1], again iterate through the array and find if there is any point whose Y coordinate is Y1 and X coordinate is (2 * reflectionX) - X1.
    • If the array does not contain the values, there is no reflection of the point [X1, Y1].
  • If we find at least one reflection for each point,
    • Return true
  • Else,
    • Return false.
Try Problem