Charles University in Prague Technical University of Ostrava Slovak University of Technology Pavol Jozef Sˇaf´arik University in Koˇsice
University of Zˇilina Masaryk University Matej Bel University in Bansk´a Bystrica University of West Bohemia
cheetahs.c, cheetahs.cpp, Cheetahs.java, cheetahs.py
A National Geographic film crew is visiting the ZOO this week. They are creating a documentary about animal speed and they would like to film one or more cheetahs running at full pace. A solitary running cheetah has been filmed successfully many times. Therefore, the crew is also after a much more spectacular feat: As many as possible cheetahs sprinting on parallel tracks filmed together in one shot.
“No, that is impossible,” said the director. “We cannot squeeze those animals into some sort of a start box, as you probably imagine, and then open the box and make them run all at once. It is clearly too dangerous and unpredictable. No.”
“Then let us make more boxes and open some of them earlier and some of them later,” said one of the filmmakers. “Could that work?”
“And if we open the boxes with the slower cheetahs a bit earlier then after a while the faster ones will be overtaking the slower ones and that would be a great shot,” pointed out another filmmaker. “We would like to see the whole pack rather short with the last animals close the leading ones. As close as possible and at least for a moment.”
It was a long and difficult discussion which ensued, but in the end the circumstances of the experiment were agreed upon.
You are given the start time and the speed of each cheetah. The length of the pack, which is defined as the distance between the first and the last cheetah in the pack, might be different at different moments. Find the minimum length of the pack during the run, where all cheetahs must be running. You may also suppose that the track is so long that the minimum length of the pack happens at least a moment before the first cheetah reaches the finish line.
All start boxes will be so close that you may consider them to be in the same place. The k-th cheetah will be released from its start box at the given time tk . at the same distance form the finish line. The k-th cheetah is expected to run the whole distance at constant speed vk .
There are more test cases. Each case occupies more lines. The first line of a case contains the number of cheetahs N (1 ≤ N ≤ 100 000). Next, there are N lines, each line contains two integers tk, vk separated by spaces and representing the start time and velocity of the k-th cheetah (1 ≤ k ≤ N ). All input values tk and rk are positive and less than 105. The input is
terminated by a line containing zero.
For each test case, print a single line with one floating point number L specifying the minimum length of the running pack. Your answer should not differ from the correct answer by more than 10−2. The length of the pack is the distance between the first and the last animal in the pack. The length can be measured at any time T ≥ max(tk ,k = 1, ..., N ). We suppose that each cheetah is running at a constant speed for all the time from the start and also at its moment of release from the start box.
2
1 1
1 1
2
1 99999
99999 99999
3
1 1
2
3
0
0.000
9999700002.000
0.500