시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB62240.000%

문제

Piggy decided to organize a biathlon race, where the competitors would compete in two disciplines. She invited N competitors, who have the following characteristics:

  • Each competitor has velocities V1 and V2, for the two disciplines, respectively.
  • The competitors have constant velocities (V1 and V2) throughout the respective tracks.
  • The distance, which a competitor covers for time t1 in the first discipline is S1 = V1t1, and the distance for the second discipline for time t2 is S2 = V2t2.
  • A competitor wins, if the sum of his times is uniquely the smallest among these of all competitors (i.e. strictly less than all the others).

As an organizer, Piggy can choose whatever distances she likes (non-negative real numbers S1 and S2) for each of the two disciplines. Now she is wondering which competitors are potential winners, that’s to say, whether there exist S1 and S2 to ensure them victory.

Write a program biathlon to determine which competitors can win.

입력

On the first line of the standard input, N is given. On the next N lines are given two positive integers V1 and V2, separated by a space: the velocities of the i-th competitor (for i=0, 1, …, N-1).

출력

On one line of the standard output, print the indexes of the competitors who can win. The indexes should be in increasing order, separated by spaces. Indexing starts from 0. This line should contain the number -1, when there is no competitor who can win.

서브태스크

번호배점제한
120

2 ≤ N ≤ 100, 1 ≤ V1, V2 ≤ 100

240

2 ≤ N ≤ 5000, 1 ≤ V1, V2 ≤ 10 000

340

2 ≤ N ≤ 100 000, 1 ≤ V1, V2 ≤ 10 000

예제 입력 1

4
1 4
2 2
4 1
3 3

예제 출력 1

0 2 3

All competitors, who can win, have the indexes: 0, 2 and 3. The one with index 0 wins for distances, for example, S1=0 and S2=10; competitor with index 2 wins for distances S1=10 and S2=0; the one with index 3 wins for some distances S1=10 and S2=10. Competitor with index 1 cannot win: he is always being defeated by competitor with index 3.

예제 입력 2

3
3 3
3 3
2 2

예제 출력 2

-1

Only competitors 0 and 1 can have minimal times, but neither of them unique. That’s why the correct output is an empty line.

채점 및 기타 정보

  • 예제는 채점하지 않는다.