2009 Canadian Computing Competition, Stage 2

Day 1, Problem 1: Invasion of the Boxen

Oh no! You are under attack by a swarm of boxen. The N (0 ≤ N ≤ 1000) boxen are all rectangular with sides perpendicular to the axes. To help you defend against these menacing boxen, you have a giant laser at your disposal.

The laser is located at the origin and shoots a single beam in some fixed specified direction. The beam, upon encountering a box, will destroy and reflect off of that box.

Beams are reflected so that if its first intersection point with a box is a horizontal segment of a box, the vertical component of the beam's direction is reversed. Similarly, the horizontal component is reversed when the beam hits a vertical segment. If the beam reflects off a corner of a box, both the horizontal and vertical components of its direction are reversed.

Output the indices of the destroyed boxes in the order that they are destroyed. It is guaranteed that no two boxes will have a common point and that no box contains the origin in its interior or boundary.

Input

The first line contains N, the number of boxen.

The second line contains two integers dx and dy (-1000 ≤ dx, dy ≤ 1000, not both zero), giving the direction in which the laser is pointed so that an unhindered beam fired from the origin will pass through (dx, dy).

The next N lines each contain 4 integers: x_i y_i w_i and h_i (where -1000 ≤ x_i, y_i ≤ 1000 and 1 ≤ w_i, h_i ≤ 1000) giving the description of the ith box which has lower left corner (x_i, y_i) and upper right corner (x_i + w_i, y_i + h_i).

Output

Suppose there are k (k > 0) boxen that are destroyed. The output contains one number per line, with the ith line (i ≤ k) containing the index of the box destroyed on the ith bounce. Notice that there is no output if k = 0.

Sample Input

3
1 -1
1 0 90 20
1 -22 90 20
1 -44 90 20

Sample Output

2
1
3

Explanation

Three boxen: box 1 covering (1, 0) to (91, 20), box 2 covering (1,-22) to (91,-2) and box 3 covering (1,-44) to (91,-24). The laser points south-east.

The beam bounces off the middle one (box 2), then into the top one (box 1) and finally destroying the bottom one (box 3).

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 128M
Added: Jun 06, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)