Mock CCO '19 Contest 1 Problem 6 - A Geometry Problem

View as PDF

Submit solution

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

Problem type

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


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.

The data guarantee that there are no two identical lines.

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

1 0
-1 0
0 0

Sample Output

1 2


There are no comments at the moment.