Determine earliest collision among moving cars

You are given n cars moving over time. Each car has known initial state at time (t=0):

• 1D case (straight road):

• initial position (x_i) (meters)

• initial velocity (v_i) (m/s)

• constant acceleration (a_i) (m/s²)

• physical size represented as a radius (r_i) (meters). (Cars collide when their intervals overlap, i.e., when center distance (\le r_i + r_j).)

• 2D case (flat plane):

• initial position ((x_i, y_i))

• initial velocity ((v_{xi}, v_{yi}))

• constant acceleration ((a_{xi}, a_{yi}))

• radius (r_i)

A car’s position evolves as:

• 1D: (x_i(t) = x_i + v_i t + \tfrac{1}{2} a_i t^2)
• 2D: (\mathbf{p}_i(t) = \mathbf{p}_i + \mathbf{v}_i t + \tfrac{1}{2} \mathbf{a}_i t^2)

Tasks

1. 1D: Determine whether any collision occurs for (t \ge 0). If yes, return the earliest collision time and the pair of cars involved.
2. 2D: Same as (1), but in 2D (cars collide when Euclidean distance between centers (\le r_i + r_j)).

Requirements

• Provide an algorithm and implementable approach.
• Discuss time complexity and how you would optimize beyond the naive (O(n^2)) pairwise checking.
• Handle edge cases such as:
• collisions at (t=0)
• cars with identical trajectories (overlapping for an interval)
• numerical precision when solving for collision times

You may assume (n) can be large (e.g., up to (10^5)), so a brute-force all-pairs solution may be too slow.