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.

- There are no vertical walls (slope equals infinity).
- No user lies on a wall (it will either be strictly above or below).
- No two walls are parallel to each other and no two walls are collinear with each other.
- Three walls do not intersect in the same point.

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 |

Tue Mar 14 18:48:15 EST 2000