845. How Many Fleets Arrive

n cars drive along a one-lane road towards a finish line at position target. Car i starts at position p[i] and travels at a constant s[i] units of distance per unit of time. All positions are distinct, and every car starts before the finish line.

Overtaking is impossible. If a car catches the one ahead, it slows to that car's speed and the two travel together from then on. A group travelling together is a FLEET; a single car on its own is also a fleet. Cars that meet exactly ON the finish line count as one fleet.

Print how many fleets cross the finish line.

target 12, positions 10 8 0 5 3, speeds 2 4 1 1 3 -> 3 target 10, positions 3 5, speeds 3 3 -> 2 target 10, positions 0 1 2 3, speeds 4 3 2 1 -> 1

In the first row the cars at 10 and 8 meet at position 12 exactly, so they count as one fleet; the car at 0 and the car at 5 arrive separately, and the car at 3 catches the one at 5.

## Turning the road into one number per car

Car i would reach the line, on its own, at time

t[i] = (target - p[i]) / s[i]

Now consider two cars with p[j] > p[i], so j is ahead. Car i catches car j before the line exactly when t[i] >= t[j]. This is the whole physics of the problem: a car that would arrive no later than the one ahead must have run into it, since it cannot have passed it.

And a fleet's arrival time is the time of its SLOWEST member, which is its leader, the car with the largest t in the group.

## The stack, and why it increases

Sort the cars by position from FRONT to BACK, that is, decreasing p. Walk them in that order keeping a stack of fleet arrival times.

if the stack is empty or t > stack top: push t this car leads a new fleet else: discard t this car joins the fleet ahead

The stack ends up holding arrival times in STRICTLY INCREASING order from the bottom up, one entry per fleet, and the answer is its height. Only the TOP is ever compared, so an implementation may keep just the current leader's time and a counter; the stack is the picture, the counter is the code. Increasing is forced by the rule: a car only survives as a leader when it is slower (larger t) than everything already in front of it.

A discarded car never returns: it has merged into a fleet whose arrival time is already on the stack, and any car behind it that catches IT also catches that fleet. That is the domination argument for this problem.

## The two traps

Sorting by position is not optional, and it must be from the finish line BACKWARDS. Processing the input order produces nonsense.

Comparing t values as floating point loses ties. Use the cross-multiplied test instead: t[i] > t[j] is exactly (target - p[i]) * s[j] > (target - p[j]) * s[i], with every factor a non-negative integer. Both products reach 10^12, so they need 64 bits, and a 32-bit multiplication here silently wraps.

## Related problems

Problem 834 keeps the survivors of a comparison in the same way and prints them instead of counting them.

## Cost

Time O(n log n), dominated by the sort; the stack pass itself is O(n). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ target ≤ 10^6` - `0 ≤ p[i] < target`, all distinct - `1 ≤ s[i] ≤ 10^6`