Count Squares from Points in the Plane
Company: 6Sense
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement `count_squares(points)`.
Given distinct 2D points with integer coordinates, count the unique squares whose four corners all occur in the input. Squares may have any orientation. Count each geometric square once.
### Constraints
- `0 <= len(points) <= 2000`
- Each point is `[x, y]` with `-10^4 <= x, y <= 10^4`.
- No duplicate points are present.
- Return a 64-bit integer count.
### Example
`[[2,1], [2,3], [4,1], [4,3], [4,5]]` returns `1`.
```hint Cover both orientations
Tests should include an axis-aligned square, a tilted square, and a rectangle that is not a square.
```
```hint Define geometric uniqueness
The same four corners must count once regardless of which corner or side an implementation considers first.
```
```hint Preserve exact comparisons
Coordinate calculations should not make a valid integer-coordinate square depend on floating-point rounding.
```
Quick Answer: Implement `count_squares(points)`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given distinct two-dimensional integer points, return the number of unique geometric squares whose four corners all occur in the input. Squares may have any orientation. Count the same four corners once regardless of which corner or side is considered first, and return a 64-bit integer count.
Constraints
- 0 <= len(points) <= 2000, and all points are distinct.
- Each point is [x, y] with integer coordinates from -10^4 through 10^4.
- Squares may have any orientation and each geometric set of four corners counts once.
- Return a 64-bit integer count and use exact integer geometry.
Examples
Input: ([],)
Expected Output: 0
Explanation: Empty input contains no square.
Input: ([[0, 0]],)
Expected Output: 0
Explanation: One point cannot provide four corners.
Hints
- Test an axis-aligned square, a tilted square, and a rectangle that is not a square.
- Include shared corners and extra points to confirm that each geometric square counts once.
- Use boundary and odd-parity coordinate combinations so valid results never depend on floating-point rounding.