LCC/Moose '20 Contest 3 J5 - Raytracing

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.5s
Memory limit: 64M

Problem type

Andy is a man who likes to think outside the box. Unfortunately for him, there is a large rectangle on the infinite 2-D plane that he is currently traveling on, with its bottom-left corner at (l, d) and its top-right corner at (r, u) (-10^9\le l < r \le 10^9, -10^9\le d < u \le 10^9).

However, Andy is also a man who plans ahead. He will start at a point (sx,sy) (-10^9\le sx \le 10^9,-10^9\le sy \le 10^9), and travel at a velocity of dx horizontal units and dy vertical units per second (-10^9\le dx \le 10^9,-10^9\le dy \le 10^9). Since Andy is a man of action, he will always be moving. This means that |dx|+|dy|>0.

Andy would like to know the times when he enters and exits the rectangle. The entering time is the first integer time since starting for when Andy is inside the rectangle. If Andy starts inside the rectangle then his entering time will be 0. The exiting time is the first integer time after the entering time for when Andy is outside the rectangle. If Andy is never inside the rectangle at an integer time, then the entering and exiting times are both -1. Note that a point on an edge of the rectangle will count as being inside.

Input Specification

The first line contains four integers l, d, r, and u.

The second line contains four integers, sx, sy, dx, dy, Andy's starting point and velocity.

Output Specification

Output two integers, the entering and exiting times.


Subtask 1 [20%]

One of dx or dy will be 0.

Subtask 2 [80%]

No further constraints.

Sample Input 1

-2 -1 3 3
-1 -2 1 2

Sample Output 1

1 3

Sample Explanation 1

Andy starts at the point (-1,-2) at time 0.

After 1 second, Andy will be at the point (0, 0), which is inside the rectangle. Therefore the entering time is 1.

After 2 seconds, Andy will be at the point (1,2).

After 3 seconds, Andy will be at the point (2,4), which is now outside the rectangle. Therefore the exiting time is 3.

Sample Input 2

-2 -1 3 3
4 1 1 1

Sample Output 2

-1 -1

Sample Explanation 2

Andy will never go inside the rectangle.


There are no comments at the moment.