Merge overlapping 2D line segments

You are given a list of 2D line segments. Each segment is represented as a list of 2D points [(x1,y1), (x2,y2), ...] that all lie on the same straight line.

Definitions

• Within a segment, the points are already sorted along the segment (from one end to the other).
• Different segments are not sorted relative to each other.
• Two segments should be merged if:
  1. They are collinear (lie on the same infinite line; i.e., same slope and offset), and
  2. Their geometric segments intersect (they share at least one point in common, including touching at endpoints).

When merging multiple segments, the result for that merged group should contain all distinct points that appear in any of the original segments in the group, sorted along the line.

Task

Return a list of merged segments (each as a sorted list of points). The order of merged segments in the output does not matter.

Example

Input

[
  [(1, 1), (2, 2), (4, 4)],
  [(2, 1), (4, 2)],
  [(3, 3), (6, 6)],
  [(7, 7), (8, 8)]
]

Output (one valid ordering)

[
  [(1, 1), (2, 2), (3, 3), (4, 4), (6, 6)],
  [(7, 7), (8, 8)],
  [(2, 1), (4, 2)]
]

Notes / Assumptions

• Coordinates are integers.
• Each input segment contains at least 2 points.
• You should remove duplicate points within a merged segment.