Osu! is a very popular music game. Basically, it is a game about clicking. Some points will appear on the screen at some time, and you have to click them at a correct time.
Now, you want to write an algorithm to estimate how diffecult a game is.
To simplify the things, in a game consisting of N points, point i will occur at time ti
at place (xi
), and you should click it exactly at ti
). That means you should move your cursor from point i to point i+1. This movement is called a jump, and the difficulty of a jump is just the distance between point i and point i+1 divided by the time between ti
. And the difficulty of a game is simply the difficulty of the most difficult jump in the game.
Now, given a description of a game, please calculate its difficulty.