Detect Squares

Medium

Math & Geometry

Design a data structure that receives a stream of points on the X-Y plane and can count axis-aligned squares.

Implement the class DetectSquares:

DetectSquares() creates an empty structure.
add(point) stores point = [x, y]. The same coordinates may be added more than once; each copy is a separate point.
count(point) returns the number of ways to choose three stored points that, together with the query point, form the four corners of an axis-aligned square with positive area (sides parallel to the axes, side length greater than 0). The query point itself is not stored by count.

Because duplicate points are distinct, choosing a different copy of the same coordinates counts as a different way.

In the examples, each call is listed in order and the output lists what each call returns (None for the constructor and add).

Example 1

Input:: DetectSquares(); add([2,1]); add([6,1]); add([2,5]); count([6,5]); add([2,5]); count([6,5]); count([4,4])
Output:: [None,None,None,None,1,None,2,0]
Explanation: The stored points (2,1), (6,1) and (2,5) complete a square of side 4 with the query (6,5), so the first count is 1. After a second copy of (2,5) is added, either copy can be used, so the count becomes 2. No square can be formed with (4,4).

Input:: DetectSquares(); add([3,5]); add([3,7]); add([5,7]); add([7,5]); add([7,7]); count([5,5])
Output:: [None,None,None,None,None,None,2]
Explanation: With the query (5,5), the points (3,5), (3,7), (5,7) form a 2 x 2 square to the left, and (7,5), (7,7), (5,7) form one to the right, so the answer is 2.

Input:: DetectSquares(); add([0,0]); add([0,2]); add([3,0]); add([3,2]); count([0,0])
Output:: [None,None,None,None,None,0]
Explanation: The four points form a 3 x 2 rectangle, which is not a square. The stored copy of (0,0) cannot help either, because a square needs positive side length.