Count Squares Formed by Intersections of Vertical and Horizontal Segments

You are given a set of vertical line segments and a set of horizontal line segments in the plane. Each segment is described by its start point and end point, and each point is an (x, y) pair. Wherever a vertical segment crosses or touches a horizontal segment, their common point is an intersection point. Picture a tic-tac-toe grid: two vertical and two horizontal strokes crossing each other enclose a square whose corners are intersection points.

Return the number of squares whose four corners are all intersection points.

The interviewer explained this problem with a drawing. After the basic version, they also asked how to find the segments that cross a given segment faster than by checking every vertical segment against every horizontal one, so be ready to discuss that.

Function Signature

def count_intersection_squares(vertical: list[list[list[int]]], horizontal: list[list[list[int]]]) -> int:

Rules

• vertical[i] = [[x1, y1], [x2, y2]] with x1 == x2 and y1 != y2. horizontal[j] = [[x1, y1], [x2, y2]] with y1 == y2 and x1 != x2. The start and end points may be given in either order.
• Segments are closed: their endpoints belong to them, so a segment that ends exactly on another segment still produces an intersection point.
• A point is an intersection point if it lies on at least one vertical segment and at least one horizontal segment.
• Count only axis-aligned squares with positive side length: four corners (x, y), (x + s, y), (x, y + s), (x + s, y + s) with s > 0, all of which are intersection points. Rectangles that are not squares do not count. Each distinct square is counted once, and squares of every size count, including squares that contain smaller ones.
• Because no two vertical segments share an x-coordinate and no two horizontal segments share a y-coordinate (see Constraints), every counted square has its four sides lying on the given segments.

Constraints

• 1 <= len(vertical) <= 300
• 1 <= len(horizontal) <= 300
• All coordinates are integers in [-10^6, 10^6].
• No two vertical segments have the same x-coordinate, and no two horizontal segments have the same y-coordinate.
• The answer fits comfortably in a 64-bit integer.

Examples

Example 1

• Input: vertical = [[[1, 0], [1, 3]], [[2, 3], [2, 0]]], horizontal = [[[0, 1], [3, 1]], [[3, 2], [0, 2]]]
• Output: 1
• Explanation: The intersection points are (1, 1), (2, 1), (1, 2) and (2, 2), the corners of one square of side 1.

Example 2

• Input: vertical = [[[0, 0], [0, 2]], [[1, 0], [1, 2]], [[2, 0], [2, 2]]], horizontal = [[[0, 0], [2, 0]], [[0, 1], [2, 1]], [[0, 2], [2, 2]]]
• Output: 5
• Explanation: The nine intersection points form a 3-by-3 grid, which contains four squares of side 1 and one square of side 2.

Example 3

• Input: vertical = [[[0, 0], [0, 4]], [[2, 0], [2, 4]], [[3, 1], [3, 4]]], horizontal = [[[0, 0], [3, 0]], [[0, 2], [3, 2]], [[-1, 3], [3, 3]]]
• Output: 2
• Explanation: The vertical segment at x = 3 starts at y = 1, so (3, 0) is not an intersection point. The squares are the one with corners (0, 0) and (2, 2) and the one with corners (2, 2) and (3, 3). The side-3 square with corners (0, 0) and (3, 3) is not counted.