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:

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.