Find intersection of two line segments
Company: Applied
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
## Problem
Given two 2D line segments **AB** and **CD**, determine whether they intersect.
Each segment is defined by its endpoints:
- A(x1, y1), B(x2, y2)
- C(x3, y3), D(x4, y4)
### Tasks
1. Return `true/false` indicating whether the two **closed** segments intersect.
2. (Optional follow-up) If they intersect at a **single point**, return that intersection point. If they overlap over an interval (collinear overlap), return an appropriate representation (e.g., "overlap" or the overlapping segment).
### Requirements / Edge cases to handle
- Vertical segments (infinite slope) and horizontal segments.
- Touching at endpoints counts as intersection.
- Collinear segments that overlap partially or fully.
- Large coordinates (avoid floating-point precision bugs if possible).
### Example
- A(0,0), B(2,2) and C(0,2), D(2,0) → intersect at (1,1)
- A(0,0), B(0,2) and C(1,0), D(1,2) → do not intersect (parallel vertical)
- A(0,0), B(2,0) and C(1,0), D(3,0) → collinear overlap
Quick Answer: This question evaluates a candidate's skills in computational geometry and numerical robustness, focusing on line-segment intersection reasoning, endpoint touching, collinearity, and precision handling.
Return whether two closed 2D line segments intersect, including endpoint touches and collinear overlap.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ((0,0),(2,2),(0,2),(2,0))
Expected Output: True
Explanation: Crossing diagonals intersect.
Input: ((0,0),(0,2),(1,0),(1,2))
Expected Output: False
Explanation: Parallel vertical segments do not intersect.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.