Canadian Computing Competition: 2020 Stage 1, Senior #1
Trick E. Dingo is trying, as usual, to catch his nemesis the Street Sprinter. His past attempts using magnets, traps and explosives have failed miserably, so he’s catching his breath to gather observational data and learn more about how fast Street Sprinter is.
Trick E. Dingo and Street Sprinter both inhabit a single straight west-east road with a particularly famous rock on it known affectionately as The Origin. Positions on this straight road ar measured numerically according to the distance from The Origin, using negative numbers for positions west of The Origin and positive numbers for positions east of The Origin.
The observations by Trick E. Dingo each contain two numbers: a time, and the value of Street Sprinter's position on the road at that time. Given this information, what speed must Street Sprinter be capable of?
The first line contains a number , the number of observations that follow. The next lines each contain an integer indicating the time, in seconds, of when a measurement was made, and an integer indicating the position, in metres, of the Street Sprinter at that time. No two lines will have the same value of .
For of the available marks, .
Output a single number , such that we can conclude that Street Sprinter’s speed was at least metres/second at some point in time, and such that is as large as possible. If the correct answer is , the grader will view as correct if .
Sample Input 1
3 0 100 20 50 10 120
Output for Sample Input 1
Explanation of Output for Sample Input 1
Since the Street Sprinter ran from position to position between time and time , we know its speed must have been at least at some point in time: if it was always less than , then the distance of could not be covered in seconds. Likewise, the speed must have been at least in order to travel between position and in seconds.
Sample Input 2
5 20 -5 0 -17 10 31 5 -3 30 11
Output for Sample Input 2