P3194 [HNOI2008] Horizontally Visible Lines

On the $x-y$ Cartesian coordinate plane, there are $n$ lines $L_1, L_2, \dots, L_n$. If, when looking downward from $y = +\infty$, some subsegment of $L_i$ is visible, we say that $L_i$ is visible; otherwise, $L_i$ is covered. For example, for the lines: $L_1: y = x$; $L_2: y = -x$; $L_3: y = 0$; then $L_1$ and $L_2$ are visible, and $L_3$ is covered. Given $n$ lines in the form $y = A x + B$ ($|A|, |B| \le 500000$), and no two lines coincide, find all visible lines.

The first line contains $N$ ($0 < N < 50000$). The next $N$ lines each contain $A_i, B_i$.

Output the indices of the visible lines in increasing order, separated by spaces. There must also be a space after the last number.

Translated by ChatGPT 5