I try to solve the following problem.
On $n$ parallel railway tracks $n$ trains are going with constant speeds $v_1$, $v_2$, . . . , $v_n$. At time $t$ = 0 the trains are at positions $k_1$, $k_2$, . . . , $k_n$. Give an $O(n\log n)$ time algorithm that detects all trains that at some moment in time are leading.
The problem is I don't know how to approach the above problem. I assume it's should very popular problem in computational geometry. I saw it few times before, but never considered to solve it.
It looks like that the problem assumes preprocessing the data before giving input the moment of time.
Complexity $O(n\log n)$ points out to process similar to sorting.
Follow-up on my comment, long for another: For any given train, the position at time $t$ is $v_it+x_{i0}$ where $v_i$ is the velocity of train $i$ and $x_i0$ is its position at $t=0$. This defines a line in the plane. The set of all lines defines a region to the left where at a given time there is at least one train to the right and a region to the right were there is no train to the right. The rightward region is convex. A train is rightmost precisely when its line is the boundary. For example, if train 1 starts at 0 with speed 1 and train 2 starts at -1 with speed 2, they meet at (1,1). Train $1$ is rightmost before $t=1$, and train $2$ is after $t=1$. If train 3 starts at -2 with speed $3/2$, it is never rightmost. If you plot the three lines you can see that. This forms the basis of my statement that you want a convex hull of the right region.