철인 2종 경기

시간 제한2초메모리 제한512 MB

요약

각 참가자의 달리기와 수영 속도가 주어질 때, 양의 구간 길이 R과 S에 따라 1등이 될 수 있는 참가자를 모두 찾는다.

난이도: 어려움10점 중 8점
유형: 기하, 정렬, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

20XX년 여름, 알고리즘 캠프에서 철인 2종 경기가 열린다. 이 경기는 달리기와 수영, 두 구간으로 이루어진다. 참가자는 먼저 $R$ 미터를 달리고, 이어서 $S$ 미터를 수영한다. 결승점에 가장 먼저 도착한 사람이 우승자가 된다. 여러 사람이 같은 시각에 도착하면 그 사람 모두 공동 우승자로 인정한다.

경기가 시작하기 전에 성관이는 참가자 $N$ 명의 자료를 살펴보고 있다. $i$ 번 참가자는 달리기 구간을 초당 $r_i$ 미터로 달리고, 수영 구간을 초당 $s_i$ 미터로 헤엄친다. 따라서 $i$ 번 참가자가 결승점에 도착하는 시각은 $\frac{R}{r_i} + \frac{S}{s_i}$ 초다.

성관이는 모든 참가자의 두 속도를 알지만 $R$ 과 $S$ 가 얼마인지는 모른다. $R$ 과 $S$ 가 0보다 큰 실수라는 것만 알고 있다. $R$ 과 $S$ 를 어떻게 정하느냐에 따라 우승자가 달라지므로, 성관이는 우승할 가능성이 있는 사람이 누구인지 궁금하다. $R > 0$ , $S > 0$ 인 실수 $R$ 과 $S$ 를 적절히 고르면 $i$ 번 참가자가 우승자 또는 공동 우승자가 되는 경우, $i$ 번 참가자는 우승할 가능성이 있다. 우승할 가능성이 있는 참가자를 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에 참가자 수 $N$ 이 주어진다. ( $1 \le N \le 200000$ )

다음 $N$ 개 줄에 참가자의 속도가 한 줄에 한 명씩 주어진다. $i$ 번째 줄에는 $i$ 번 참가자의 수영 속도 $s_i$ 와 달리기 속도 $r_i$ 가 이 순서대로 주어진다. 수영 속도가 먼저 온다는 점에 주의한다. 두 값 모두 자연수다. ( $1 \le s_i, r_i \le 10000$ )

출력

우승할 가능성이 있는 참가자의 번호를 오름차순으로 한 줄에 모두 출력한다. 번호는 공백 하나로 구분한다.

예제2

예제 1
입력
```
3
1 3
2 2
3 1
```
예상 출력
```
1 2 3
```
예제 2
입력
```
3
1 2
1 1
2 1
```
예상 출력
```
1 3
```