Geometry is about boundary rules

Build three tools:

• Signed orientation plus bounds for closed segments.
• An active count with an explicit tie convention.
• Closest pair recursion returning both distance and y order.

Predict endpoint contact, duplicates, and extreme coordinates before ordinary cases.

Opposite sides of which segment?

AB: (0,0)→(2,0). CD: (3,-1)→(3,1).

C and D straddle the infinite line through AB. Do the segments intersect?

No. A and B are on the same side of CD's line. Proper crossing requires opposite signs in both orientation pairs.

Zero orientation needs bounds

Collinear segments [0,2] and [3,5] have all four orientations zero, but no intersection.

[0,2] and [2,5] share an endpoint and do intersect.

For a collinear point, check both inclusive coordinate ranges. This also handles a segment reduced to a point.

Three intervals meet at 3

Intervals: [1,3], [3,3], [3,5].

Successor events, combined by coordinate:

For ordinary closed-endpoint events instead, process starts before ends at a tie. Do not mix the two conventions.

The closest pair can cross the split

Points in x order: (-4,0), (-1,3) | (1,3), (5,0).

Left answer: 18. Right answer: 25.

The crossing pair (-1,3), (1,3) has squared distance 4.

Returning only the smaller child answer misses it.

Return y order to make merging cheap

Each child returns (best squared distance, points in y order).

Merge those orders. Keep points with (x-splitX)^2 < d2.

Scan later strip points until dy^2 >= d2. The packing argument bounds candidates by a constant; the scan order must be y order.

Re-sorting each recursive strip changes O(n log n) to O(n log² n).

Distance bounds include the initial value

Extreme pair: (-10^9,-10^9) and (10^9,10^9).

Squared distance: 8*10^18, which fits signed 64-bit arithmetic.

A minimum initialized to 1<<62 is already smaller than the answer. Use a real pair or a valid larger sentinel.

Compare orientation signs directly; multiplying their values can overflow.

Reconstruct a complete solution

• Segments: four orientations, collinear bounds, then strict sign comparisons.
• Overlap: choose one event convention and handle ties consistently.
• Closest pair: split by x index, remember split x, recurse, merge by y, inspect strip.
• Zero or one point returns 0; duplicate entries may also return 0.

Explain the invariant before submitting each exercise.