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 |
|
|