Lamp
Time limit5sMemory limit512 MB
Given rectangular windows on two parallel walls 10 m apart and a lamp on one wall, count the windows of the lamp's building whose interior any reflected ray can reach.
- Level
Hard8 of 10
- Topics
- Geometry, Implementation, Math, Simulation
- Solved
- No attempts yet
Problem
In the middle of the night, Bitratio switched on the lamp at the entrance of the building where Byteasar lives, and the harsh light now keeps Byteasar awake. The lamp does not shine straight onto his windows, but its light reaches them after reflecting off other windows. Byteasar wonders whether his neighbours suffer the same way, that is, whether the light reaches their windows too. He asks you to write a program that answers this.
Byteasar lives in building , which has windows. The lamp sits on the wall at the very bottom of this building. Directly opposite, exactly meters away, stands another building with windows, whose wall is parallel to the wall of .
Light obeys geometric (ray) optics: it travels along straight rays, and whenever a ray strikes a window it is reflected, the angle of reflection equal to the angle of incidence.
Coordinate systems are placed on both walls as follows. On each wall the axis is horizontal and the axis is vertical; the axes on the two walls point the same way, and the two origins face each other. Every window (on either building) is a rectangle with sides parallel to the axes. A ray is reflected only in the interior of a window; on a window's boundary it is absorbed. Within one building, no two windows share any interior point. The lamp lies on the wall of building at the point , which is neither inside nor on the boundary of any window.
Input
The first line contains two integers and (), separated by a single space: the number of windows in building and in building , respectively.
Each of the next lines describes one window of building . Line (for ) contains four integers , , , (, ), separated by single spaces: the -th window of building is the rectangle whose lower-left corner is and whose upper-right corner is , in meters.
The following lines describe the windows of building in the same format.
Output
On the first line, print the number of windows of building whose interior is struck by at least one ray. It is guaranteed that in every test there is at least one such window (Byteasar's own).
On the second line, print the indices of those windows (windows are numbered from ) in increasing order, separated by single spaces.