Laser Tag

Interview

Time limit1sMemory limit128 MB

Summary
Find every firing angle from the origin whose laser beam returns to the origin after at most 7 reflections off flat mirrors, and print the angles in order.
Level

Medium7 of 10

Topics
Geometry, Simulation, Implementation
Solved
No attempts yet

Problem

A laser-tag arena contains several upright, double-sided flat mirrors, each tall enough that the arena can be treated as a 2D plane seen from above. A mirror reflects your laser beam, so a beam you fire can bounce off one or more mirrors and travel back to the exact point you fired from — hitting you. Your task is to find every initial firing angle whose beam comes back to the firing point, so that those angles can be avoided.

The mirrors are not perfectly reflective, so only beams that return after at most 7 reflections need to be considered. Put the firing point at the origin of a Cartesian coordinate system, with positive xx pointing right and positive yy pointing up. Each mirror is a straight segment of negligible thickness whose both faces reflect. A firing angle is measured in degrees counterclockwise from the positive xx-axis and rounded to the nearest degree, giving an integer from 00 to 359359.

Input

The input contains one or more datasets. Each dataset begins with a line holding the number of mirrors nn (1≤n≤71 \le n \le 7). Each of the next nn lines contains four integers x1 y1 x2 y2x_1\ y_1\ x_2\ y_2 — the coordinates of the two ends of one mirror. All coordinates are integers whose absolute value is less than 10001000. No two mirrors intersect or touch, and no mirror passes through the origin.

The input ends with a line containing a single 00, which is not processed.

Output

For each dataset, print one line. Consider every beam that leaves the origin and returns to the origin after at most 77 reflections; round each such firing angle to the nearest degree and normalize it to the range 0≤a≤3590 \le a \le 359. Remove duplicate angles and print the remaining integers in increasing order, separated by single spaces. If no beam returns to the origin, print no danger instead.

No beam grazes the exact end of a mirror. Although the reported angles are rounded, all internal computation should use double-precision floating point. No output line exceeds 7979 characters.

Examples4

  1. Example 1

    Input
    2
    2 1 -1 4
    -2 4 -2 -1
    4 
    3 10 13 10
    -13 17 -7 23
    33 17 27 23
    10 -10 20 -10
    3
    3 10 13 10
    -13 17 -7 23
    33 17 27 23
    0
    
    Expected output
    45 67 90 135 157 180
    29 61 63 117
    no danger
    
  2. Example 2

    Input
    2
    2 1 -1 4
    -2 4 -2 -1
    0
    
    Expected output
    45 67 90 135 157 180
    
  3. Example 3

    Input
    4
    3 10 13 10
    -13 17 -7 23
    33 17 27 23
    10 -10 20 -10
    0
    
    Expected output
    29 61 63 117
    
  4. Example 4

    Input
    3
    3 10 13 10
    -13 17 -7 23
    33 17 27 23
    0
    
    Expected output
    no danger