Migrated from Lutece 122 Visible Segments

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

The central problem to computer graphics is rendering, where we only display visible objects for a given viewpoint. The problem in general, in three dimension world with arbitrary shape, is very difficult. As a student in college, you are encouraged to study some simpler cases at first.

Here we describe a special case of visibility problem. The scenario is restricted to a plane, and the object is only segment. Initially, lots of disjoint segments are placed in the plane arbitrarily. The viewpoint $p$ is fixed at the origin (i.e. $(0, 0)$), and doesn’t lie on any of the segments. Our task is to determine all the segments we can see from $P$. More precisely, a segment $S$ can be seen from $P$ if and only if there exists a point $q$ on $S$, the segment $\overline{pq}$ doesn’t intersect any segment $S’$ other than $S$. For example, the following figure has three non-visible segments from $p$, they are $L_1$, $L_3$ and $L_0$.

Input

The first line contains one integer $n$ ($0 < n \leq 100,000$), which is the number of segments. Followed are $n$ lines, where each line contains four integers $x_1$, $y_1$, $x_2$, $y_2$ ($-10,000 \leq x_1, y_1, x_2, y_2 \leq 10,000$) to represent two end points $(x_1, y_1)$ and $(x_2, y_2)$ of a segment.

Output

List all visible segments in ascending order (each one in a line, index starts from $0$).

Samples

4
1 1 2 2
-2 -4 1 -4
-1 -2 2 -2
-3 0 0 3

2
3

Note

1. Given any segment $S$, whose two ends are $v_1$ and $v_2$. $S$ is invisible to $p$ if $p$, $v_1$ and $v_2$ are collinear;
2. Given any two segments $S_1$ and $S_2$, $v_1$ is one of $S_1$’s end points, and $v_2$ is one of $S_2$’s. If $v_2$ is on the line of $\overline{pv_1}$, we say $v_2$ is not visible to $p$.

You can notice these two cases in the figure; they are $L_1$ and $L_3$ respectively.

Resources

The 8th UESTC Programming Contest Final