WatchtowerSpotlight | Topcoder Archive

Problem Statement

You are trying to drive across enemy lines under the cover of darkness in order to get to your main objective. The enemy has erected a watchtower that is outfitted with a radar device. The device emits a directional pulse that rotates counterclockwise at a given rate. You are given its coordinates, the number of seconds it takes for it to make a complete revolution, and the distance the pulse can detect. The field of view of the radar pulse covers the following angular interval at time t seconds:

[(t % s) * 360 / s, (t % s) * 360 / s + 360 / s].

Here % denotes the modulus operator. Note that the field of view forms an angle that might not be integral, the interval is inclusive on both ends, and the interval boundaries are measured counterclockwise from the line emanating from the tower in the positive x direction. If you are further than d away (using standard cartesian distance) from the watchtower, you will not be seen by the radar, regardless of which direction it is pointing. However, if you are exactly d away, you are still within range. The radar pulses once at each integer value of t.

You are given the starting coordinates (your location at t = 0 seconds), and the coordinates of your target location. You now wish to get to your target location as quickly as possible. However, you cannot risk being captured by the enemy, and as such, can never be at a location that is within the field of view of the radar pulse. Similarly, you can never be at the same location as the watchtower, since you would surely be spotted by the enemies manning the tower. Also, you can never stop, for you would surely be spotted by ground forces. Therefore, your path must be planned such that you avoid the radar pulse, taking into account the rate of rotation.

You may move one unit up, down, left or right each second, but may never remain at your current location or move diagonally. If you are on coordinate (x, y) at time t seconds, then (x, y) must not be within the field of view of the radar pulse or at the watchtower at t seconds. This includes second 0, and the second you reach the target. For example, suppose you are at location (3,7) at time 0 and decide to move to location (3,8). Then (3,7) at time t=0 and (3,8) at time t=1 should not be visible from the tower.

You are given Strings start and end, each in the form "x y" (quotes added for clarity) indicating the start and end coordinates. You are also given a String watchtower, which is in the form "x y s d" (quotes added for clarity), providing the coordinates of the watchtower, the number of seconds it takes for the radar to make one revolution, and the distance the radar can detect.

Because of the layout of the terrain, the starting location, ending location, tower location, and all points travelled must be within the grid from (0,0) to (49,49), inclusive.

You are to return an int indicating the minimum number of seconds it takes to reach your destination while staying out of radar view. If it is not possible to reach your destination without getting caught, return -1.

Definition

Class:: WatchtowerSpotlight
Method:: quickestEscape
Parameters:: String, String, String
Returns:: int
Method signature:: int quickestEscape(String start, String end, String watchtower)
(be sure your method is public)

Constraints

start will be in the form "x y". (quotes added for clarity)
end will be in the form "x y". (quotes added for clarity)
start and end will denote distinct points.
watchtower will be in the form "x y s d". (quotes added for clarity)
All x and y values will be integers between 0 and 49, inclusive.
s will be an integer between 2 and 99, inclusive.
d will be an integer between 1 and 50, inclusive.
The radial edges of the view area will not be within 1e-6 of a degree of a grid point, other than those with the same x or y coordinate as the tower. Grid points are all points with integer coordinates between 0 and 49 inclusive.
The integers specified in the inputs will not have leading zeros.

Examples

```
"0 0"
```
```
"10 10"
```
```
"7 3 10 5"
```
```
Returns: 20
```
Here, the watchtower has a range of 5 units. So, if we head up 10 units, and then right 10 units, we can stay completely outside the field of view of the watchtower. This takes us 20 seconds.
```
"0 0"
```
```
"10 10"
```
```
"3 7 9 4"
```
```
Returns: 20
```
Here, we could still start out heading upward but avoiding the radar would slow us down. A quicker route is to first go right 10 units, then up 10 units.
```
"0 0"
```
```
"10 10"
```
```
"9 9 3 5"
```
```
Returns: 32
```
We head towards our target location, but must carefully avoid the radar once we are near it.
```
"0 0"
```
```
"49 49"
```
```
"24 24 5 40"
```
```
Returns: -1
```
The radar is rotating too fast, and can see a long distance. We can't possibly get to our target without being spotted.
```
"0 0"
```
```
"26 26"
```
```
"24 24 20 30"
```
```
Returns: 52
```
```
"10 13"
```
```
"10 11"
```
```
"5 10 70 6"
```
```
Returns: 4
```
Here, we can't go directly down. We have to move at least one second out of the way for the radar to pass.
```
"20 20"
```
```
"21 20" 
```
```
"0 0 4 50"
```
```
Returns: -1
```
The target is close, but you are caught by the radar before you can move.
```
"0 0"
```
```
"0 1"
```
```
"0 1 99 10"
```
```
Returns: -1
```
Your clever enemy built the watchtower on top of the target!

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.