Determine whether points form squares

# Determine whether points form squares You are given points in the plane with integer coordinates. A square has four equal positive side lengths and four right angles. Its sides need not be parallel to the coordinate axes, and the input points are not ordered around the shape. ### Part 1 — Validate four points Implement `validSquare(p1, p2, p3, p4) -> bool`, returning whether the four points are the vertices of a non-degenerate square. Each point is a two-element array `[x, y]`. Repeated coordinates cannot form a valid square. The source exercise uses `-10000 <= x, y <= 10000`. The existing broader interview variant permits any signed 32-bit integer coordinates; explain how your arithmetic remains exact for that range. Its list-based interface, `is_square(points)`, receives the same four points in one list. ```text p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1] result = true p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12] result = false p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1] result = true ``` #### What This Part Should Cover - Independence from input order and orientation. - Rejection of coincident points, collinear points, and shapes that satisfy only some of the square conditions. - Exact arithmetic, correctness, and the time and space cost for four points. ### Part 2 — Count squares among many points Given `N` points, count the distinct geometric squares whose four vertices occur in the input. A square counts once regardless of vertex order. Repeated input coordinates do not create additional geometric squares or degenerate squares. Implement `count_squares(points) -> int`. This interpretation matches the existing counting variant. The original interview prompt also asks you to clarify duplicate handling: discuss separately how the answer would change if distinct input occurrences at the same coordinate were considered different choices. Do not mix that alternative with the geometric count. #### Constraints - `1 <= N <= 20000` for the optimization discussion. - Coordinates are signed 32-bit integers. - Rotated squares count. - You may assume constant average-time hash lookups when discussing the requested bounds. ```text points = [[0,0], [1,0], [1,1], [0,1], [0,0]] geometric square count = 1 ``` If input occurrences were counted separately instead, the two occurrences of `[0,0]` would give two choices for that square. Explain a baseline taking about `O(N^4)` time, an improvement taking about `O(N^3)`, and an approach taking about `O(N^2)`. These are algorithmic comparison targets; no wall-clock performance guarantee is specified for `N = 20000`. #### What This Part Should Cover - A counting rule that neither misses rotated squares nor counts the same geometric square repeatedly. - A clear duplicate policy and its effect on the alternative occurrence count. - The three requested time bounds, auxiliary storage, and arithmetic range. ### What a Strong Answer Covers The answer solves both validation and counting, explains why every counted shape meets the square definition, and accounts for repeated discoveries and repeated input coordinates. It distinguishes the source's four-argument API from the broader list-based variants. ### Follow-up Questions - How would you check the result when there are fewer than four distinct coordinates? - Which intermediate quantities can exceed the coordinate type's range even though every input coordinate fits in that type?