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 ﬁlm crew is visiting the ZOO this week. They are creating a documentary about animal speed and they would like to ﬁlm one or more cheetahs running at full pace. A solitary running cheetah has been ﬁlmed successfully many times. Therefore, the crew is also after a much more spectacular feat: As many as possible cheetahs sprinting on parallel tracks ﬁlmed 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 ﬁlmmakers. “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 ﬁlmmaker. “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 diﬃcult 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 deﬁned as the distance between the ﬁrst and the last cheetah in the pack, might be diﬀerent at diﬀerent 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 ﬁrst cheetah reaches the ﬁnish 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 ﬁnish 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 ﬁrst 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 ﬂoating point number L specifying the minimum length of the running pack. Your answer should not diﬀer from the correct answer by more than 10−2. The length of the pack is the distance between the ﬁrst 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