Optimizing Split for Ironman Duo Competition

The Ironman Duo Competition is a traditional sports event at Jilin Education Institute, consisting of a long‐distance run and a cycling race. The race is divided into two segments: a running segment of distance \(k\) kilometers and a cycling segment of distance \(r\) kilometers, where \(s = k + r\) is the total race distance. Each contestant has different strengths; some excel in running, while others in cycling. For a fixed total distance \(s\), a larger \(k\) favors strong runners, and a smaller \(k\) favors strong cyclists.

Given the total distance \(s\) and the average running and cycling speeds of each contestant, you are to determine the most favorable split \(k\) and \(r\) for a specified contestant so that he/she becomes the champion with the maximum possible winning margin. That is, choose \(k\) and \(r\) (with \(k + r = s\)) such that the target contestant’s total time is less than all other contestants’ times, and the minimum time difference (margin) between the target and any other contestant is maximized.

The time taken by a contestant with running speed \(v_r\) and cycling speed \(v_c\) is given by:

[ T = \frac{k}{v_r} + \frac{s-k}{v_c} ]

If the target contestant has speeds \(a\) (running) and \(b\) (cycling), and another contestant has speeds \(u\) and \(v\), then the difference in finishing times is

[ f(k) = \frac{k}{u} + \frac{s-k}{v} - \left(\frac{k}{a} + \frac{s-k}{b}\right) = k\left(\frac{1}{u} - \frac{1}{a} - \frac{1}{v} + \frac{1}{b}\right) + s\left(\frac{1}{v} - \frac{1}{b}\right). ]

For each competitor (other than the target), define:

[ A = \left(\frac{1}{u} - \frac{1}{a}\right) - \left(\frac{1}{v} - \frac{1}{b}\right) \quad\text{and}\quad B = s\left(\frac{1}{v} - \frac{1}{b}\right). ]

Your task is to choose \(k\) in the interval \([0, s]\) (with \(r = s-k\)) to maximize the winning margin \(M(k)\), where

[ M(k) = \min_{\text{other contestants}} {A \cdot k + B}, ]

subject to the condition that for all other contestants \(A \cdot k + B > 0\) (so that the target contestant wins).

inputFormat

Input begins with a line containing three numbers: an integer \(n\) (the number of contestants, \(n \ge 2\)), a real number \(s\) (the total distance), and an integer \(p\) (the 1-indexed index of the target contestant). The following \(n\) lines each contain two real numbers. The \(i\)-th line provides the running speed and cycling speed of the \(i\)-th contestant.

It is guaranteed that there is at least one split \(k\) (with \(0 \le k \le s\)) such that the target contestant wins the race, and that the answer is unique up to an absolute or relative error of \(10^{-6}\).

outputFormat

Output two real numbers: \(k\) and \(r = s - k\) representing the optimal distances for running and cycling, respectively. Print the numbers with at least 6 decimal places of precision.

sample

2 10 1
10 20
20 10

0.000000 10.000000