Author: | A. Baranov | Time limit: | 1 sec | |
Input file: | Standard input | Memory limit: | 256 Mb | |
Output file: | Standard output |
Vasya writes a 2D game engine. One of the tasks is to determine parts of the scene visible by the gamer from a given position.
Let us consider a set of rectangles with sides parallel to the coordinate axes: Pi = {(x, y): ai ≤ x ≤ bi, ci ≤ y ≤ di}.
Rectangle Pi is visible from the point A, if there exists some point B ∈ Pi such that segment AB does not contain points belonging to other rectangles.
Your program must determine indices of rectangles that are visible from the point (0, 0).
Input contains integer n followed by 4 × n integers: ai, bi, ci and di.
Output must contain indices of visible rectangles in ascending order. Indices start from 0.
Rectangles do not intersect each other and do not contain point (0, 0).
2 ≤ n ≤ 105
− 106 ≤ ai ≤ bi ≤ 106
− 106 ≤ ci ≤ di ≤ 106
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|