Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 20m 21s17 days 22 hours 20 minutes 21 seconds.

Advanced - Geometry · 4:04

Lines & Segment Intersection

A segment PQ spans the line Ax + By + C = 0 with A = Py - Qy, B = Qx - Px and C = -A·Px - B·Py; dividing by the gcd and fixing the sign makes equal lines give equal triples. Two lines meet by Cramer's rule, whose denominator is zero exactly for parallel lines. Two segments intersect when both pairs of orientation signs disagree (a zero counts as touching), and when all four signs are zero the segments are collinear and the overlap of their projections decides; finding the intersection then yields empty, a point or a segment, with __int128 for the large intermediate values.

You will learn

Convert a segment into an integer line Ax + By + C = 0 and normalise it with the gcd and a sign rule
Intersect two lines with Cramer's rule and recognise parallel and coincident lines from the determinants
Decide whether two segments intersect with four orientation signs, including touching and the collinear projection case
Report the intersection as empty, a point or a segment with exact arithmetic, handling point-sized segments and overflow

Chapters

PreviousOrientation & Oriented Triangle Area: the Turn Test NextPolygon Area, Pick's Theorem & Lattice Points