Hide

Problem C
Ray Chasing

Ray tracing is becoming very popular in modern video games. You decide to brush up on the topic. After reading a bit of the math behind how it works, you feel the need to get a bit of hands-on experience. So you consider the following simple problem that does not involve any reflections of the ray.

Given a box with sides parallel to the $x$- and $y$-axes of the Euclidean plane, you emit a ray starting from some point in the interior of the box. Calculate which side of the box is first hit by the ray. If the ray perfectly hits a corner, you should indicate both sides of the box that meet at that corner.

\includegraphics[width=0.45\textwidth ]{figure.pdf}
Figure 1: Illustration of the second test case. The ray starting at $(0,0)$ and passing through $(-3,3)$ will pass through the top-left corner of the box.

Input

The first line of input consists of four integers $X_1, X_2, Y_1, Y_2$. These give the coordinates of the sides of the box. The second line contains four integers $X_ s, Y_ s, X_ r, Y_ r$ describing two points $X_1 < X_ s < X_2, Y_1 < Y_ s < Y_2$ and $(X_ s, Y_ s) != (X_ r, Y_ r)$ (i.e. the points are distinct). This indicates the ray starts at point $(X_ s, Y_ s)$ and travels in the direction that passes through $(X_ r, Y_ r)$. All integers in the input will lie between $-10^4$ and $10^4$ (inclusive). Note, the point $(X_ r, Y_ r)$ may lie inside the box, on the boundary of the box, or even outside the box; it merely indicates the direction the ray is travelling.

Output

If the ray does not hit a corner of the box, print the appropriate string left, right, bottom, or top indicating which side was hit by the ray. These correspond to the following ranges of coordinates.

  • The left side is $\{ (X_1, y) : Y_1 \leq y \leq Y_2\} $.

  • The right side is $\{ (X_2, y) : Y_1 \leq y \leq Y_2\} $.

  • The bottom side is $\{ (x, Y_1) : X_1 \leq y \leq X_2\} $.

  • The top side is $\{ (x, Y_2) : X_1 \leq y \leq X_2\} $.

If the ray hits a corner of the box, output the corresponding hyphenated string indicating which corner was hit: top-left, top-right, bottom-left, or bottom-right.

Sample Input 1 Sample Output 1
-2 2 -2 2
0 0 2 2
top-right
Sample Input 2 Sample Output 2
-2 2 -2 2
0 0 -3 3
top-left
Sample Input 3 Sample Output 3
-2 2 -2 2
0 0 -1 -2
bottom
Sample Input 4 Sample Output 4
-10 12 17 24
-9 23 -7 12
bottom

Please log in to submit a solution to this problem

Log in