143. Detect Squares Rotated along the XY Plane

Detect Squares Rotated along the XY Plane

You are given a stream of points on the X-Y plane.

Design a data structure that supports adding points from the stream and counting how many squares can be formed with a given query point.

Unlike the simpler axis-aligned version, the square may be rotated at any angle on the plane.

Duplicate points are allowed and must be treated as different points.

For a query point, count the number of ways to choose three points already added to the data structure such that those three points together with the query point form a square with positive area.

A valid square must satisfy all of the following:

All four vertices are distinct point instances, although duplicate coordinates may exist in the data structure.
All four sides have the same positive length.
The two diagonals have the same midpoint.
The two diagonals have the same length.

Class Name

DetectSquares

DetectSquares()
Initializes the object with an empty data structure.

Method Signatures

void add(List<Integer> point)
Adds a new point to the data structure.

int count(List<Integer> point)
Counts the number of ways to choose three previously added points such that those three points and the query point form a square with positive area, where the square may be rotated at any angle.

Parameter Details

point.size() == 2
point.get(0) is the x-coordinate
point.get(1) is the y-coordinate

Important Notes

Duplicate points are allowed and must be counted separately.
The query point itself is not automatically part of the data structure unless it was previously added using add.
A square must have positive area, so four collinear points do not form a valid square.
The square does not need to be parallel to the x-axis or y-axis.

Constraints

point.size() == 2
0 ≤ x, y ≤ 1000
At most 3000 calls in total will be made to add and count.

Examples

Example 1

DetectSquares detectSquares = new DetectSquares()
detectSquares.add(point = List.of(1, 0))
detectSquares.add(point = List.of(2, 1))
detectSquares.add(point = List.of(1, 2))
detectSquares.count(point = List.of(0, 1))

Output:
1

Explanation:
The query point is (0, 1).

The three previously added points are (1, 0), (2, 1), and (1, 2).

Together with the query point, they form a rotated square with vertices:
(0, 1), (1, 0), (2, 1), (1, 2)

So the answer is 1.

Example 2

DetectSquares detectSquares = new DetectSquares()
detectSquares.add(point = List.of(1, 0))
detectSquares.add(point = List.of(2, 1))
detectSquares.add(point = List.of(1, 2))
detectSquares.add(point = List.of(2, 1))
detectSquares.count(point = List.of(0, 1))

Output:
2

Explanation:
The coordinate (2, 1) was added twice, and duplicate points are treated as different point instances.
So there are two different ways to choose three added points that, together with query point (0, 1), form the same rotated square.

Example 3

DetectSquares detectSquares = new DetectSquares()
detectSquares.add(point = List.of(1, 1))
detectSquares.add(point = List.of(2, 2))
detectSquares.add(point = List.of(3, 3))
detectSquares.count(point = List.of(0, 0))

Output:
0

Explanation:
All available points are collinear, so no square with positive area can be formed.