Determine whether points form squares

Problem: Square detection and counting from point coordinates

You are given points on a 2D plane with integer coordinates.

Part A — Validate a single square

Given exactly 4 points [(x1,y1), (x2,y2), (x3,y3), (x4,y4)], determine whether these 4 points can be the vertices of a non-degenerate square (square may be rotated; sides are not necessarily axis-aligned).

Output: true if they form a square, otherwise false.

Part B — Count squares in a set (with optimization)

Given N points (may contain duplicates; treat duplicates as separate inputs but they should not create degenerate “squares”), count how many distinct squares can be formed whose 4 vertices are all present in the set.

• A square is considered the same regardless of the order of its vertices.
• Squares may be rotated.

Follow-up:

1. Describe a brute-force approach (e.g., around $O(n^4)$).
2. Improve it to about $O(n^3)$.
3. Further improve to about $O(n^2)$ time (assume hash set / hash map lookups are $O(1)$ average).

Constraints (assume typical interview constraints)

• 1 <= N <= 2e4 (for the optimized discussion)
• Coordinates fit in 32-bit signed integers

Clarify any additional assumptions you need (e.g., whether duplicates should be ignored by converting to a set).

Validate a Single Square

You are given exactly 4 points on a 2D plane with integer coordinates as a list points = [[x1,y1],[x2,y2],[x3,y3],[x4,y4]].

Determine whether these 4 points can be the vertices of a non-degenerate square. The square may be rotated (sides are not necessarily axis-aligned). A set of points where two or more coincide, or where the points are collinear, is not a valid square.

Return true if they form a square, otherwise false.

Approach hint: Compute all 6 pairwise squared distances. A square has exactly 4 equal smallest distances (the sides) and 2 equal largest distances (the diagonals), where diagonal² = 2 × side², and side² must be greater than 0. Using squared distances keeps everything in integer arithmetic and avoids floating-point error.

Constraints

• Exactly 4 points are provided.
• Coordinates fit in 32-bit signed integers.
• Coincident points or collinear points do not form a square.
• The square may be rotated (not necessarily axis-aligned).

Examples

Example 1

Input: [[0,0],[0,1],[1,1],[1,0]]
Output: True

Explanation: Unit axis-aligned square.

Example 2

Input: [[0,0],[2,1],[3,-1],[1,-2]]
Output: True

Explanation: Rotated square with side² = 5 and diagonal² = 10.

Hints

1. Avoid floating point: compare squared distances so all math stays in integers.
2. Collect all 6 pairwise squared distances and sort them.
3. A valid square: the 4 smallest are equal (sides, > 0) and the 2 largest are equal and equal to 2× the side² (diagonals).

Count Squares in a Point Set

You are given N points on a 2D plane with integer coordinates as a list points = [[x,y], ...]. The input may contain duplicate coordinates; duplicates should be collapsed (they cannot help form a square).

Count how many distinct squares can be formed whose 4 vertices are all present in the set. A square is the same regardless of the order of its vertices, and squares may be rotated.

Optimization story (this is exactly the interview follow-up):

• Brute force: try every 4-tuple of points and test if they form a square — about O(n^4).
• Better: fix one side (a pair of points) and derive the other two vertices — about O(n^3).
• Best (implemented here): iterate over every pair of points treated as a diagonal, derive the other two vertices via the perpendicular-diagonal formula, and check membership in a hash set — about O(n^2) with O(1) average lookups. Each square is discovered via both of its diagonals, so divide the final count by 2.

Given a diagonal with endpoints (x1,y1) and (x2,y2), the other two vertices are ((x1+x2 + y1-y2)/2, (y1+y2 + x2-x1)/2) and ((x1+x2 - y1+y2)/2, (y1+y2 - x2+x1)/2). They count only when those coordinates are integers and both are present in the set.

Constraints

• 1 <= N <= 2e4 for the optimized discussion.
• Coordinates fit in 32-bit signed integers.
• Duplicate coordinates are collapsed and cannot form a square.
• A square counts once regardless of vertex order; rotated squares count.

Examples

Example 1

Input: [[0,0],[0,1],[1,1],[1,0]]
Output: 1

Explanation: A single unit square.

Example 2

Input: [[0,0],[0,1],[1,1],[1,0],[2,0],[2,1]]
Output: 2

Explanation: A 2x3 grid of points forms two adjacent unit squares.

Hints

1. Put all distinct points in a hash set for O(1) average membership tests.
2. Treat each pair of points as a diagonal of a candidate square; the perpendicular bisector of equal length gives the other two vertices.
3. Derived vertex coordinates may be non-integer (half values) — skip those (a real lattice square would land on integer coordinates).
4. Each square has two diagonals, so it is counted twice — divide the total by 2.