[HNOI2008] 水平可见直线
题目描述
在 $x-y$ 直角坐标平面上有 $n$ 条直线 $L_1,L_2,…L_n$,若在 $y$ 值为正无穷大处往下看,能见到 $L_i$ 的某个子线段,则称 $L_i$ 为可见的,否则 $L_i$ 为被覆盖的。
例如,对于直线:
$L_1:y=x$;
$L_2:y=-x$;
$L_3:y=0$;
则 $L_1$ 和 $L_2$ 是可见的,$L_3$ 是被覆盖的。给出 $n$ 条直线,表示成 $y=Ax+B$ 的形式($|A|,|B| \le 500000$),且 $n$ 条直线两两不重合,求出所有可见的直线。
输入输出格式
输入格式
第一行为 $N$ ($0<N<50000$),接下来的 $N$ 行输入 $A_i,B_i$
输出格式
从小到大输出可见直线的编号,两两中间用空格隔开,最后一个数字后面也必须有个空格。
输入输出样例
输入样例 #1
3
-1 0
1 0
0 0
输出样例 #1
1 2