Count Squares Formed by Segments

# Count Squares Formed by Segments You are given axis-aligned line segments with integer coordinates. Each segment is represented by two endpoints. One input list contains only vertical segments and another contains only horizontal segments. Count the distinct axis-aligned squares whose four complete sides are covered by the supplied segments. A valid square is defined by `x1 < x2` and `y1 < y2` such that `x2 - x1 == y2 - y1`, both vertical sides cover the full range `[y1, y2]`, and both horizontal sides cover the full range `[x1, x2]`. Implement: ```python def count_squares( vertical: list[tuple[tuple[int, int], tuple[int, int]]], horizontal: list[tuple[tuple[int, int], tuple[int, int]]], ) -> int: ... ``` ## Constraints and Clarifications - Endpoint order is arbitrary; normalize every segment. - Zero-length segments do not form a side. - Collinear segments may overlap or touch. Their union can cover a square side, and the same geometric square is counted once regardless of how many source segments cover it. - Intersections at endpoints count. - Coordinates may be negative. - Do not assume the drawing is a complete grid. - Discuss a baseline approach and how you would index candidate counterpart segments to avoid blindly testing every set of four input segments. ## Hints - Normalize collinear coverage before counting to prevent duplicates. - A pair of parallel sides determines the only possible side length and the required positions of the other pair. - Consider indexing intervals by their fixed coordinate and supporting fast coverage queries on the varying coordinate.