33648번 - 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.

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.

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) \ne (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.

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≤y≤Y_2\}$.
• The right side is $\{(X_2,y):Y_1≤y≤Y_2\}$.
• The bottom side is $\{(x,Y_1):X_1≤y≤X_2\}$.
• The top side is $\{(x,Y_2):X_1≤y≤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.