Math and Geometry
Counting shapes with a hash map
Geometry that is really Unit 1: fix one thing, look up what the others would have to be.
Key idea
The geometry is thin
Counting axis-aligned squares among a set of points sounds geometric. It is the complement map from Unit 1 with coordinates instead of numbers.
The move is the same: rather than searching for a shape, fix part of it, compute what the rest would have to be, and look those up.
Why it works
Fix the diagonal, and the other corners are determined
Take the query point and any other point that could be its diagonal opposite. For an axis-aligned square that means the two differ in both coordinates by the same non-zero amount.
Once those two corners are fixed, the other two are completely determined: they are the combinations of the two x values with the two y values. So the count contributed is the product of how many points sit at each of those two positions.
No searching, no geometry beyond that observation. The rest is bookkeeping.
Below, one query point is tested against three candidates, and for the one that qualifies the other two corners are read straight off the coordinates.
Gotcha
Exclude the zero-size case
Two points with equal coordinate differences includes the case where both differences are zero, which is the query point itself. That would count a square of no size.
The guard px == qx rules it out, because a genuine diagonal partner must differ in both coordinates. Checking only that the differences match is the common error and it inflates every count.
Tip
Counting duplicate points
If two points sit at the same position, each copy forms a distinct square, so a corner appearing twice doubles the count for every square that uses it. Multiplying together how many points sit at each of the three derived corners handles that automatically.
Using a set instead of a counter would silently collapse duplicates and undercount. Whether duplicates are distinct is a question the problem must answer, and the data structure follows from it.
Cost
Cost
Each query scans the distinct positions once and does constant work, so it is linear in the number of distinct points. Adding a point is constant.
The alternative of checking every pair per query is quadratic. The saving comes from deriving the other corners rather than searching for them, which is the same trade as the complement map.
Predict the output: counting points that sit on top of each other
Three corners of a square are fixed, and one of them has two points at the same position. Type the two lines it prints.
Detect Squares
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.