Yesterday, a new attraction was opened at the local funfair: a hall of mirrors. This is a labyrinth in which all the walls are covered with mirrors so that visitors lose their sense of direction in a sea of reflections. The layout of the labyrinth can be described by a polygon with all sides parallel to either the x-axis or y-axis.
On the opening day, many visitors got so lost that the ride operators had to intervene and help them find their way out. To better understand where visitors get lost the most, the operators decided to install a monitoring system. This system involves an invisible laser beam running through the hall of mirrors at foot level, so that the movement of the visitors can be tracked by observing when and where the laser beam gets interrupted.
The laser beam starts at some boundary point of the polygon at an angle of $$$45$$$ degrees to the wall. Whenever it hits a mirror, it bounces off in a $$$90$$$ degree angle. To get their monitoring system to work, the operators are planning to install sensors at each of the first $$$m$$$ bouncing points of the laser beam. Find the locations where the sensors need to be installed.
The input consists of:
Additionally, the input satisfies the following constraints:
Output $$$m$$$ lines, each with two integers $$$x$$$ and $$$y$$$, giving the coordinates of the bounce locations in order.
4 6 0 0 10 0 10 10 0 10 1 0
10 9 9 10 0 1 1 0 10 9 9 10
10 10 -2 -2 8 -2 8 8 4 8 4 0 2 0 2 6 -4 6 -4 2 -2 2 4 1
8 5 5 8 4 7 8 3 3 -2 -4 5 -3 6 2 1 -1 -2 -2 -1
Name |
---|