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).