2172. 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.

Constraints - `1 ≤ n ≤ 200` - `-10^9 ≤ p[i] ≤ 10^9`, strictly increasing - `1 ≤ s[i] ≤ 10^9` - `d[i]` is 1 or -1 - motion is continuous, so a meeting can happen at a half position at a half time - both particles in a collision are destroyed at that instant and take no further part - when several collisions share one instant, every particle involved in any of them is destroyed