A quad-tree recursively divides a two-dimensional region into four quadrants. The first operation needed to build one is assigning points to the four children of a split.
Design a QuadTreePartitioner class:
QuadTreePartitioner() creates a stateless partitioner.int[] quadrantCounts(int[][] points, int cx, int cy) returns the number of points in each quadrant around (cx, cy).
Use half-open boundaries so every point belongs to exactly one quadrant:
- A point is east when
x >= cx; otherwise it is west. - A point is north when
y >= cy; otherwise it is south.
Return counts in the order [NE, NW, SW, SE]. Each call is independent.
Example 1:
Input:
Output:
Explanation: (1,1) and (2,3) are northeast. The other three points occupy northwest, southwest, and southeast once each.
Example 2:
Input:
Output:
Explanation: (5,5) is northeast because equality belongs to east and north. (4,5) is northwest and (5,4) is southeast.
Constraints
0 <= points.length <= 10^5points[i].length == 2-10^9 <= points[i][0], points[i][1], cx, cy <= 10^9- At most
100 calls are made to quadrantCounts.
Count Quad-Tree Quadrantsmedium