Loading problem…
You are given a stream of points on the X-Y plane. Design an algorithm that: - Adds new points from the stream into a data structure. Duplicate points are allowed and should be treated as different points. - Given a query point, counts the number of ways to choose three points from the data structure such that the three points and the query point form an axis-aligned square with positive area. An axis-aligned square is a square whose edges are all the same length and are either parallel or perpendicular to the x-axis and y-axis. Implement the DetectSquares class: - DetectSquares() Initializes the object. - void add(int[] point) Adds a new point point = [x, y] to the data structure. - int count(int[] point) Counts the number of ways to form axis-aligned squares with point point = [x, y] as described above.
Example 1
Input: operations = ["DetectSquares","add","add","add","count","count","add","count"], arguments = [[],[[3,10]],[[11,2]],[[3,2]],[[11,10]],[[14,8]],[[11,2]],[[11,10]]]
Output: [null,null,null,null,1,0,null,2]
Explanation: The first count at (11,10) finds one square using (3,10), (3,2) and (11,2), with side 8. The query (14,8) forms no square with the stored points, so it returns 0. After (11,2) is added a second time, each copy forms its own square, so the last count returns 2.
Example 2
Input: operations = ["DetectSquares","add","count"], arguments = [[],[[0,0]],[[1,1]]]
Output: [null,null,0]
Explanation: Only (0,0) is stored. A square with (1,1) would also need (0,1) and (1,0), which are missing, so the count is 0.
Example 3
Input: operations = ["DetectSquares","add","add","add","add","count"], arguments = [[],[[0,0]],[[0,1]],[[1,0]],[[1,1]],[[0,0]]]
Output: [null,null,null,null,null,1]
Explanation: The four corners of the unit square are stored. Querying (0,0) uses (0,1), (1,0) and (1,1) to form exactly one square.
For a query point, a square is fixed once you pick the diagonally-opposite corner. Enumerate stored points as that diagonal corner and multiply the counts of the two remaining corners.
Run checks all cases above. Submit evaluates all test cases.