Collisions in Time Order
n particles sit on a line. Particle i starts at position p[i], travels at
speed s[i], and moves right if d[i] is 1 or left if d[i] is -1. Positions
are distinct and given in increasing order. Motion is continuous, not in whole
steps, so two particles can meet at a half position at a half time.
two particles COLLIDE the instant they are at the same position.
both are destroyed at that instant, and take no further part.
destruction is instantaneous, so a particle destroyed at time T is already
gone at time T and cannot collide with anything else later.
if several collisions happen at the SAME instant, every particle involved in
any of them is destroyed.
no particle ever changes speed or direction.
Print how many particles are never destroyed, then their indices in increasing
order, all on one line separated by single spaces. If none survive, print just
0.
## What most people try first
The one stack sweep from #168, which is the right answer there and the wrong answer here. #168 gives every asteroid the SAME SPEED and no positions, so meetings happen in left to right order and a single pass over the list is enough. Two things break that here:
1. with individual speeds, the nearest pair is not always the first to meet,
so the ORDER of collisions is an order on TIME and not on position.
2. a faster particle can catch a slower one going the SAME WAY, which cannot
happen at all when every speed is equal.
``` 3 particles: (0, speed 5, right) (10, speed 1, right) (20, speed 1, left)
particles 1 and 2 approach each other over a gap of 10 at a combined speed of 2, so they would meet at time 5. particle 0 catches particle 1 over a gap of 10 at a closing speed of 5 - 1 = 4, so they meet at time 2.5, which is EARLIER. so 0 and 1 are destroyed at 2.5, and particle 2 then has nothing left to meet. -> 1 2 ```
## When does a given pair meet
For i < j, so p[i] < p[j], with gap = p[j] - p[i]:
d[i] = 1, d[j] = -1 approaching time gap / (s[i] + s[j])
d[i] = 1, d[j] = 1 i catches j time gap / (s[i] - s[j]) if s[i] > s[j],
otherwise never
d[i] = -1, d[j] = -1 j catches i time gap / (s[j] - s[i]) if s[j] > s[i],
otherwise never
d[i] = -1, d[j] = 1 separating never
## Why a pair's meeting time can be computed once and never revisited
No particle changes speed or direction, ever. So the position of particle i
at time T is p[i] + d[i] * s[i] * T for as long as it exists, and the
instant at which a given pair would coincide is a property of the input alone.
A collision removes particles; it never alters how the remaining ones move. So
the schedule of candidate meetings is fixed before anything happens, and the
only thing a collision changes is which of those meetings actually takes place.
That is what makes the whole problem finite: repeatedly take the earliest
meeting between two surviving particles, destroy everyone involved at that
instant, and repeat. Each round destroys at least two particles, so there are
at most n / 2 rounds.
## Comparing two times without dividing
A meeting time is a fraction a / b with b > 0. Comparing a1 / b1 against
a2 / b2 by floating point loses the tie cases, and ties matter here because
simultaneous collisions are resolved together. Cross multiply instead:
a1 / b1 < a2 / b2 exactly when a1 * b2 < a2 * b1, since both denominators
are positive.
## Overflow
That cross multiplication is where the width goes. A gap is at most
2 * 10^9, since positions run to 10^9 in magnitude, and a denominator is at
most 2 * 10^9, since it is a sum of two speeds. So a product reaches
4 * 10^18. That FITS in a signed 64 bit integer, whose top is about
9.22 * 10^18, and it is nowhere near a 32 bit one, whose top is
2147483647. So every product must be 64 bit, and a declared test exists on
which a 32 bit build orders two candidate times the wrong way round and names
the wrong survivor.
## Cost
O(n^3) in the worst case, since each of up to n / 2 rounds scans all pairs,
and O(n) memory. At n = 200 that is a few million operations.