## CCO '09 P1 - Invasion of the Boxes

View as PDF

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 128M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### Canadian Computing Competition: 2009 Stage 2, Day 1, Problem 1

Oh no! You are under attack by a swarm of boxes. The boxes are all rectangular with sides perpendicular to the axes. To help you defend against these menacing boxes, 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 Specification

The first line contains , the number of boxes.

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

The next lines each contain 4 integers: , , and where and giving the description of the th box which has lower left corner and upper right corner .

#### Sample Input

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

#### Description of Sample Input

Three boxes: box 1 covering to , box 2 covering to and box 3 covering to . The laser points south-east.

#### Output Specification

Suppose there are boxes that are destroyed. The output contains one number per line, with the th line containing the index of the box destroyed on the th bounce. Notice that there is no output if .

#### Output for Sample Input

2
1
3

#### Description of Output for Sample Input

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