Biathlon#8568
Piggy decided to organize a biathlon race in which competitors will compete in two disciplines. She invited competitors, each having the following characteristics:
Each competitor has velocities v_1 and v_2 for the two disciplines, respectively.
Competitors move with constant velocities (v_1 and v_2) on each respective track.
The distance that a competitor covers in time t_1 in the first discipline is s_1 = v_1 t_1, and the distance in the second discipline covered in time t_2 is s_2 = v_2 t_2.
A competitor wins if the sum of his times is uniquely the smallest among all competitors (that is, strictly less than all the others).
As the organizer, Piggy may choose any distances she likes for each of the two disciplines -- that is, any non-negative real numbers s_1 and s_2. Now, she wonders which competitors could be potential winners; in other words, whether there exist s_1 and s_2 that allow a competitor to secure victory.
Write a program to determine which competitors can win.
The first line contains (2 \le n \le 10^5). The next lines each contain two positive integers v_1 and v_2 (1 \le v_1, v_2 \le 10^4): the velocities of the -th competitor (for i = 0, 1, \dots, n - 1).
Output a single line containing the indices of competitors who can win, in increasing order, separated by spaces. Indices start from . If no competitor can win, output .
Example 1
Example 2
First example. All competitors who can win have indices , , and . The competitor with index wins, for example, if s_1 = 0 and s_2 = 10; the competitor with index wins if s_1 = 10 and s_2 = 0; the one with index wins for some distances, e.g., s_1 = 10 and s_2 = 10. Competitor cannot win since competitor always defeats them.
Second example. Only competitors and can have the minimal time, but neither uniquely. Therefore, the correct output is .