I am interested resolving a programming challenge problem, but I’m struggling obtaining an efficient solution.

Consider yourself as a point located on the origin $ (0,0)$ of an infinite two-dimensional flat world. There are $ n$ sea waves surrounding you, each one modeled as a circle with center $ (x_i, y_i)$ , initial radius $ r_i$ , and propagation speed $ s_i$ , so that the radius of wave $ i$ as a function of the time $ t ≥ 0$ is $ r_i + s_i \cdot t$ . You choose any fixed direction and run “forever” at speed $ p$ . Will you be able to scape?

Some helpful restrictions given as assumptions are provided:

- $ 1 ≤ p ≤ 1000$
- $ 3 ≤ n ≤ 10^4$ [the number of circles $ c_i$ ]
- $ −1000 ≤ x_i,\;y_i ≤ 1000$
- $ 1 ≤ r_i ≤ 1000$
- $ 0 ≤ s_i < p$
- Except for $ n$ , all numbers are real, with at most three digits after the decimal point.
- Initially, you are strictly outside all the waves.
- There are not precision errors.

My solution so far is quite simple (I have programmed it in C++):

- Each “fixed direction” to run forever is solely determined by the angle of that line with the X axis, namely $ 0 \leq \theta < 2 \pi$ .
- For each $ \theta \in [0, 0.001, 0.002, \dots, 2\pi)$ :
- Recall that the map is within the square $ [-1000, -1000]$ to $ [1000, 1000]$ , and the furthest distance between $ (0,0)$ and any point in the map has distance $ 1000\sqrt{2}$ . We advance at $ p$ speed, so at most we will compute $ 1000\sqrt{2}/p \approx 1414/p$ iterations.
- For each $ t \in [0, 0.001, 0.002, \dots, 1414/p]$ :
- My position at time $ t$ in line $ \theta$ is $ pos_t = (\cos \theta \cdot t \cdot p, \sin \theta \cdot t \cdot p)$ .
- Check whether $ pos_t$ is inside any sea wave at moment $ t$ . Basically, check if the distance between $ pos_t$ and the center of each circle is less than that circle’s radius at moment $ t$ , namely $ r_i + s_i \cdot t$ . If so, bad luck; we’re done with this $ \theta$ and we continue the search.
- If not, try with next $ t$ .

- If no intersection is found after iterating all $ t$ s, then you will be able to scape (through line with angle $ \theta$ ).

- If all $ \theta$ s got some intersections, then we are not able to scape.

This solution has cost $ \Theta(6000 \times 1400 \times n)$ , which is impractical for $ n \leq 10^4$ . Informally, and without being precise, the multiplicative term may be $ O(n^3)$ if $ n \leq 10^4$ is considered. Plus, it may not be correct, as I am assuming that $ \Delta t = 0.001$ is fine; same for the angle.

I have thought about another idea, which is reducing systematically $ \theta$ . For instance, let’s imagine that we’ve got a circle at $ C = (5, 5)$ (in the line of $ \theta = \pi/2$ ) with some small radius. From the beginning, we know that angles $ \theta = \pi/2 \pm \alpha$ will never be an option, being $ \alpha$ determined by tangent lines from $ (0, 0)$ to $ C$ and $ t$ ; the more time passes, the higher $ \alpha$ will be and thus the wider will be this range of restricted angles.

So, at moment $ t$ we have a set of ranges of possible $ \theta$ s, and that range is reduced as long as $ t$ increases (unless all waves have speed 0, for sure).

But how to continue from there? I see the same problems as with my implementation: determining $ \Delta t$ and $ \Delta \theta$ .

I ask for your help to find a better algorithm. I suspect that there may be an algorithm that is just $ O(k n)$ or $ O(k \cdot n \log n)$ with $ k$ being reasonably small.