This problem was used in the following GFU competitions:
GFU 2024 D2 Q2
GFU 2024 D1 Q2
You’d like to figure out whether a car was speeding while it was driving down a straight road. Unfortunately, you don’t have any radar guns or related instruments for measuring speed directly; all you have are photographs taken of the car at various checkpoints on the road at various times. Given when and where these photographs were taken, what is the fastest speed that you can prove the car must have been going at some point along the road?
The first input will be a single integer n that represents the number of data sets that follow. Each data set will start with a single integer x (2 <= x <= 100), the number of photographs taken. For each of the following x photographs, there will be two integers: t (0 <= t <= 10,000) the time the photograph was taken and d (0 <= d <= 1,000,000) the distance from the camera. The first photo is always taken at time 0 and distance 0. Both time and distances strictly increase.
Output the greatest integral speed that you can be certain that the car was going at some point.
Example Input:
2
2
0 0
7 42
5
0 0
5 24
10 98
15 222
20 396
Example Output:
6
34
This is a pretty simple program... no real tips/tricks.