A Geometry Problem

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 162M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

N lines are drawn in the xy-plane. List the lines which have a segment of positive length that is visible from y = +\infty.

Constraints

1 \le N \le 5 \cdot 10^4

-5 \cdot 10^5 \le A_i, B_i \le 5 \cdot 10^5

In test data worth 30% of marks, you may assume N \le 5000.

Input Specification

The first line contains a single positive integer, N.

Each of the next N lines contains two space-separated integers A_i and B_i, indicating that a line of the form y = A_i x + B_i is drawn. These lines have IDs from 1 to N in input order.

Output Specification

Output on a single line, in increasing order, the IDs of the lines which are visible. The list should be space-separated.

Sample Input

3
1 0
-1 0
0 0

Sample Output

1 2

Comments

There are no comments at the moment.