Problem B
Hall O' Wee Mirrors

For the autumn harvest festival coming up, you and your friend are designing a house that has a lot of fun rooms. In one, you are going to set up a whole lot of double-sided mirrors so that as a person walks through, they see reflections of themselves. You realize that the mirrors may not be lined up the way you want, so you want to write a program to identify the mirrors in which you can see your reflection when you stand in various places in the room. You have chosen excellent-quality mirrors — each one is vertical, perfectly flat, and covers from the floor to the ceiling. You should assume that all standing locations are points and all mirrors are very thin.

\includegraphics[width=0.36\textwidth ]{sample_1} \includegraphics[width=0.44\textwidth ]{sample_2}
Figure 1: Illustration of the sample input cases.


Input is up to $100$ configurations of mirrors and standing locations. Each configuration start with an integer $1 \le n \le 100$, followed by $n$ lines that each describe a mirror. Each mirror description has four integers $x_1~ y_1~ x_2~ y_2$, where $(x_1,y_1)$ and $(x_2,y_2)$ are the corners of the mirror.

The mirror descriptions are followed by an integer $1 \le m \le 100$, which indicates the number of standing locations. Each of the next $m$ lines contains a pair of integer coordinates $x~ y$ describing the location where a person may stand in the room.

All coordinates are in the range $[-100,100]$. All points within a case are unique. No standing location is on any mirror. Input ends when $n$ is zero.


For each room and each standing location, indicate the number of mirrors in which you can see your own reflection. From that location you should look at mirrors everywhere in the room. You may ignore the issue that one mirror may block your view of another mirror, and you should ignore reflections that use multiple mirrors.

Sample Input 1 Sample Output 1
2 1 2 5
-3 3
-3 6
3 5
2 -1 4 1
-2 -1 -4 1
0 3
0 -1
-3 -1

CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Greg Hamerly
Source Baylor Competitive Learning course
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in