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.

Part 1: Earliest Collision Time on a Line with Constant Acceleration

You are given n point vehicles moving on a 1D line. Vehicle i starts at x0[i], has initial velocity v0[i], constant acceleration a[i], and follows x_i(t) = x0[i] + v0[i] * t + 0.5 * a[i] * t^2 for continuous time t >= 0. Return the earliest time when any two vehicles occupy the same position. If several pairs collide at the same earliest time, return the lexicographically smallest pair (i, j) with i < j so the result is deterministic. Return None if no collision exists. A baseline O(n^2) pair scan is acceptable; as a follow-up, think about pruning or event-based methods under restricted motion patterns.

Constraints

• 0 <= n <= 2000
• len(x0) == len(v0) == len(a)
• -1e6 <= x0[i], v0[i], a[i] <= 1e6
• Continuous time with t >= 0
• Use a floating-point tolerance of about 1e-9

Examples

Example 1

Input: ([0.0, 10.0], [2.0, -3.0], [0.0, 0.0])
Output: (2.0, (0, 1))

Explanation: The positions are x0(t) = 2t and x1(t) = 10 - 3t. They meet at t = 2.

Example 2

Input: ([0.0, 4.0, 100.0], [0.0, 0.0, 0.0], [2.0, 0.0, 0.0])
Output: (2.0, (0, 1))

Explanation: Vehicle 0 follows x(t) = t^2, so it reaches x = 4 at t = 2 and collides with vehicle 1 first.

Hints

1. For a fixed pair (i, j), subtract the two motion equations. You get at most a quadratic equation in t.
2. Be careful with degenerate cases: the quadratic term may disappear, and sometimes two vehicles share the exact same trajectory, which means the earliest collision is t = 0.

Part 2: Earliest Intersection Time for Moving Disks in 2D

You are given n vehicles modeled as disks in 2D. Vehicle i starts at p0[i] = (x0, y0), moves with constant velocity v[i] = (vx, vy), and has radius r[i]. Its center follows p_i(t) = p0[i] + v[i] * t for continuous time t >= 0. Return the earliest time when any two disks intersect, meaning the distance between centers is at most r[i] + r[j]. If several pairs intersect at the same earliest time, return the lexicographically smallest pair (i, j) with i < j so the result is deterministic. Return None if no intersection ever happens. Count already-overlapping disks as colliding at t = 0, and use a floating-point tolerance around 1e-9.

Constraints

• 0 <= n <= 2000
• len(p0) == len(v) == len(r)
• -1e6 <= coordinates and velocity components <= 1e6
• 0 <= r[i] <= 1e6
• Continuous time with t >= 0
• Use a floating-point tolerance of about 1e-9

Examples

Example 1

Input: ([(0.0, 0.0), (10.0, 0.0)], [(1.0, 0.0), (-1.0, 0.0)], [1.0, 1.0])
Output: (4.0, (0, 1))

Explanation: The centers start 10 units apart and close at relative speed 2. They first touch when the center distance becomes 2, which happens at t = 4.

Example 2

Input: ([(0.0, 0.0), (1.0, 0.0), (10.0, 0.0)], [(0.0, 0.0), (0.0, 0.0), (0.0, 0.0)], [1.0, 1.0, 1.0])
Output: (0.0, (0, 1))

Explanation: Disks 0 and 1 already overlap at time 0 because their centers are 1 unit apart and their radii sum to 2.

Hints

1. For one pair of disks, switch to relative motion: treat one disk as stationary and let the other move with the relative velocity.
2. After squaring the distance condition, you get a quadratic inequality At^2 + Bt + C <= 0. Already-overlapping disks correspond to C <= 0 at t = 0.