Wireless communication can be affected by regions of interference, due to effects such as the presence of magnetic fields near power lines. In this assignment you are give a set of lines describing where interference is present, and you are to determine where a user can roam without encountering interference. Each line is defined by the equation
where a and b are two real numbers. Think of each line as defining a interference wall of infinite length. This wall splits every point in the plane into one of three classes, those lying above the wall (having larger y-coordinate), those lying below (having smaller y-coordinate), and those lying on the wall. Altogether, these walls split the plane into regions, called zones.
A wireless user is given by a point (x,y), which we assume does not lie on one of the walls. Your task is to determine which zone contains the user. The zone is described by indicating those lines that make up the boundary of the zone.
For example, consider the walls shown in the figure below. The user at point (4,7) is in the zone (darker shaded) bounded by walls 0, 2, and 3 (note that wall 1 does not touch the zone). The user at point (10.5, 4.5) is in the zone (lighter shaded) bounded by walls 1, 2, and 3.
Write a program which inputs a list of walls, given by their a and b values, and a list of users, given by their (x,y) coordinates. For each user, determine which zone it lies in. Output only the walls that bound this zone, and indicate whether the user is above or below each such wall.
The first line of input contains the number of walls, say n. After this there are n lines, each containing the a and b value for the coefficients of a wall. After this there is a list of users, each given by its x and y coordinates on one line. The list of users is terminated by the coordinates ``999 999''. You may assume that there are at most 100 walls and 100 users. Point coordinates and line coefficients should be represented as doubles. You should not make any assumptions about the sizes of these numbers.
You may make the following assumptions about the positions of walls.
For each user you should output the coordinates of the user on the first line. Then on separate lines give the wall indices (numbered from 0 to n-1) which bound the zone. The walls must be given in increasing order of wall index. Points should be output in the form ``(x, y)'' (note the space between the comma and the y coordinate).
The example below shows the input and output for the situations shown in the figure above.
Input :
4 1.0 4.0 0.5 1.0 0.0 6.0 -1.0 12.0 4.0 7.0 10.5 4.5 999 999
Output:
The zone for (4, 7) is bounded by walls
0
2
3
The zone for (10.5, 4.5) is bounded by walls
1
2
3
| Input 1 | Output 1 |
|---|---|
| Input 2 | Output 2 |
| Input 3 | Output 3 |
| Input 4 | Output 4 |
| Input 5 | Output 5 |
| Input 6 | Output 6 |
| Input 7 | Output 7 |