ad-hoc, basic geometry
Given a set of lattice points, find the minimum number of points that should be added to this set such that there exist at least one square with vertices on the points of the extended set.
Even though it is not mentioned in the problem statement that all points of the set are distinct, and we are only interested in non-degenerate square (square with non-zero size), the test cases had only distinct set of points. Nevertheless, allowing degenerate square does not make the problem any harder. We can compute the minimum number of addendum points to create a degenerate and non-degenerate square, and then take the minimum of the two.
A degenerate square will have all four vertices at the same location. Hence, we just need to find the frequency of the point that occurs most number of times in the set. If the frequency x is >= 4, then we already have a degenerate square and the answer should be zero, otherwise we need to add (4 - x) copies of this point to get a degenerate square.
Now, we can assume that all points in the set are distinct. We can first consider some basic cases:
- If the set is empty, then we need to add 4 points.
- If the set has only one point, then we need to add 3 points to make a square
- If the set has only two points then we can add two more points to make a square.
The only interesting case is when we have 3 or more points, in which case the answer should be 0, 1, or 2. We only need to check, if there is already an square in the set (in which case the answer should be zero), or if there are three vertices of a square present in the set (in which case the answer should be 1). If none of the two cases hold, then the answer must be 2, as we can always pick two points from the set and add two more points to make a square (explained in the next section).
Extend Square with Two Points:
Suppose we have two points A (x1, y1) and B (x2, y2), and we want to create a square whose edge is the line segment joining the two points. Let us call this square ABCD, so we need to find the co-ordinates of C and D.
In a complex plane, the ray segment AB can be represented as
AB = (x2 - x1) + i (y2 - y1)
Since the length of AB and AD is the same and the angle between them is 90 degrees, the ray segment AD can be obtained by rotating AB to 90 degrees. In other words
AD = AB * (cos 90 + i sin 90)
AD = -(y2 - y1) + i (x2 - x1)
which can be used to compute the co-ordinate of D, i.e.,
D = (x1 - (y2 - y1), y1 + (x2 - x1))
Also note that the ray segment AD and BC are the same in the complex plane, hence we can use the same to compute the co-ordinates of C, i.e.,
C = (x2 - (y2 - y1), y2 + (x2 - x1))
Note that, in the above explanation we rotated AB to clockwise by 90 degrees. On the other hand, if we rotate AB anti-clockwise by 90 degrees, we will find a different square.
Check if Three/Four Vertices of Square Exist in the Set:
If there are three or more vertices of the square are present in the set, then two of these points would be the consecutive vertices of the underlying square. Hence, we can iterate through all pair of points in the set, create a square with the two points making an edge of the square, and check how many of the remaining vertices (which we can compute as explained in the previous section) of the square exist in the set. If for any pair, we have both remaining points in the set, then we already have a square. If for any pair, we have one of the remaining points in the set, then we have three vertices of the square.
Note that, one must consider both squares that can be formed by considering the line segment joining the two points as an edge.
In order to test the membership of a point in the set, one could use a set (which has O (lg N) query time), or a hash table with a properly chosen hash function (which will have O (1) amortized query time).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be put up soon.
Tester’s solution will be put up soon.