Merge Overlapping Straight Fence Runs From a Property Survey

A land survey records fence lines as a list of straight runs. Each run is a list of integer survey points [x, y], all lying on one straight line, already given in order along that line. Different runs can lie on the same line and physically overlap — for example, two separate survey passes that both recorded part of the same fence.

Consolidate the input into the fewest runs that represent the same physical fence layout: wherever two or more runs sit on one line and connect end to end, fold them into a single run carrying every point from the group.

Your function needs to handle every orientation correctly, including perfectly horizontal and perfectly vertical runs — don't assume every run has a well-defined, finite slope.

Function signature

def merge_fence_runs(runs: list[list[list[int]]]) -> list[list[list[int]]]:

runs[i] is the list of [x, y] points making up run i.

Rules

• Treat two runs as being on the same infinite line only when every point from both, taken together, satisfies one shared linear equation; runs on two different lines stay separate forever, regardless of whether they physically cross paths or meet at a single shared point.
• Define a run's span as everything between its first and last point along its own line. For two runs confirmed to share a line, they're combinable the moment their spans have any point in common, and sharing just an endpoint is enough to count.
• Merging is transitive: if run A overlaps run B, and run B overlaps run C, all three combine into one run even if A and C don't directly overlap.
• Each output run is the sorted, deduplicated set of points from all of its merged input runs, sorted by x ascending, then by y ascending.
• Output order: whichever input run shows up earliest in the input list determines where its line's group slots into the output; within one line's group, if the runs didn't all connect into a single piece, list the separate pieces sorted by their own first point.

Examples

Example 1 — diagonal runs that chain together

runs = [[[0, 0], [2, 0], [4, 0]], [[4, 0], [6, 0]], [[9, 0], [11, 0]], [[0, 1], [0, 4]]]
merge_fence_runs(runs)
-> [[[0, 0], [2, 0], [4, 0], [6, 0]], [[9, 0], [11, 0]], [[0, 1], [0, 4]]]

The first two runs share (4, 0) and merge. The third run is on the same horizontal line but has a gap (from 6 to 9), so it stays separate. The fourth run is vertical, a different line entirely.

Example 2 — no merges needed

runs = [[[1, 1], [2, 2]], [[5, 0], [5, 3]]]
merge_fence_runs(runs) -> [[[1, 1], [2, 2]], [[5, 0], [5, 3]]]

One diagonal run and one vertical run on entirely different lines, so both pass through unchanged.

Constraints

• 1 <= len(runs) <= 10^4
• 2 <= len(runs[i]) <= 100, with at most 10^5 points total across all runs.
• Coordinates are integers and stay within [-10^4, 10^4].
• Points within a run are distinct, collinear, and already given in order along the line.
• Different runs may share points or be exact duplicates of each other.