Solution
Approach 1: Iterate Triangles
Intuition
For each triangle, let's try to find the 4th point and whether it is a rectangle.
Algorithm
Say the first 3 points are p1, p2, p3
, and that p2
and p3
are opposite corners of the final rectangle. The 4th point must be p4 = p2 + p3  p1
(using vector notation) because p1, p2, p4, p3
must form a parallelogram, and p1 + (p2  p1) + (p3  p1) = p4
.
If this point exists in our collection (we can use a HashSet
to check), then we should check that the angles of this parallelogram are 90 degrees. The easiest way is to check the dot product of the two vectors (p2  p1)
and (p3  p1)
. (Another way is we could normalize the vectors to length 1, and check that one equals the other rotated by 90 degrees.)
Complexity Analysis

Time Complexity: , where is the length of
points
. 
Space Complexity: .
Approach 2: Iterate Centers
Intuition
Consider opposite points AC
and BD
of a rectangle ABCD
. They both have the same center O
, which is the midpoint of AC
and the midpoint of AB
; and they both have the same radius dist(O, A) == dist(O, B) == dist(O, C) == dist(O, D)
. Notice that a necessary and sufficient condition to form a rectangle with two opposite pairs of points is that the points must have the same center and radius.
Motivated by that result, let's classify each pair of points PQ
by their center C
= the midpoint of PQ
, and the radius r = dist(P, C)
. Our strategy is to brute force on pairs of points with the same classification.
Algorithm
For each pair of points, classify them by center
and radius
. We only need to record one of the points P
, since the other point is P' = 2 * center  P
(using vector notation).
For each center
and radius
, look at every possible rectangle (two pairs of points P, P', Q, Q'
). The area of this rectangle dist(P, Q) * dist(P, Q')
is a candidate answer.
Complexity Analysis

Time Complexity: , where is the length of
points
. It can be shown that the number of pairs of points with the same classification is bounded by  see this link for more. 
Space Complexity: .
Analysis written by: @awice.