Detect earliest collision among moving cars

You are given **n vehicles** with kinematics parameters. A “collision” means two vehicles occupy the same position at the same time. Assume continuous time, **t ≥ 0**. ## Part A (1D) Each vehicle i moves on a line with **constant acceleration**: - Inputs (arrays of length n): - `x0[i]` (float): initial position - `v0[i]` (float): initial velocity - `a[i]` (float): constant acceleration - Motion model: - `x_i(t) = x0[i] + v0[i] * t + 0.5 * a[i] * t^2` **Task:** Write a function that returns the **earliest collision time** `t*` and one pair `(i, j)` that collides at `t*`, or report **no collision**. Notes/assumptions: - Vehicles are treated as **points** (ignore length). - A collision between i and j occurs if there exists some `t ≥ 0` such that `x_i(t) = x_j(t)`. - If multiple collisions happen at the same earliest time, returning any one is fine. - Discuss time complexity; give a baseline approach and at least one optimization idea. ## Part B (2D extension) Now each vehicle moves in 2D (you may assume **constant velocity** for this part to keep the math tractable): - Inputs: - `p0[i] = (x0[i], y0[i])` - `v[i] = (vx[i], vy[i])` - `r[i]` (radius) - Motion model: - `p_i(t) = p0[i] + v[i] * t` **Task:** Determine the earliest time `t*` when any pair of disks intersects, i.e. when `||p_i(t) - p_j(t)|| ≤ r[i] + r[j]`, or report **no collision**. State clearly how you handle edge cases like already-overlapping vehicles at t = 0 and floating-point precision.