Intersection of O(n) expanding circles with line from the origin

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

• 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

• 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 a

The solution outline:

Step 1. Verify, that all the initial (at the moment $t=0$) wave circles don't contain your starting point $(0,0)$. If yes, then continue - otherwise exit, no escape.

Step 2. For each wave circle $W_i$ you need to find an escape sector - the range of directions, where the escape is guaranteed.

Imagine a circle of your possible positions at moment $t$ with center in $(0,0)$ and radius $pt$ - we'll call it the circle $C$. Let's consider what will happen with circles $C$ and $W_i$ with time. Originally (when $t=0$) the circle $C$ is just a point at $(0,0)$. Then, with time increasing, the expanding circle $C$ will at first touch the expanding circle $W_i$ at a single point, then intersect it at two points. Moving further, at some point of time the expanding circle $C$ will touch the circle $W_i$ again at a single point, then it will contain the circle $W_i$ completely (because $p \gt s_i$).

Two intersection points between circles $C$ and $W_i$ define a no-escape sector. This sector angle $\alpha$ grows from zero to some maximal value and then decreases to zero again. Cosine of this half-angle at the moment of time $t$ can be found from the triangle with all known sides:

$$\cos(\frac {\alpha} {2}) = \frac {(pt)^2+d_i^2-(r_i+s_it)^2} {2d_ipt}$$

where $d_i = \sqrt{x_i^2+y_i^2}$.

You need to find positions of intersection points, which will give you this maximal angle value. In order to do that you can take first derivative of the non-escape sector half-angle by time and set it to zero - that will give you the moment of time when the non-escape sector is maximally wide. This moment of time $T_i$ will be:

$$T_i = \sqrt{\frac{d_i^2-r_i^2}{p^2-s_i^2}}$$

Knowing the non-escape sector you'll easily find the escape sector.

Step 3. If intersection of all the escape sectors is non-empty, then the escape is possible.

The algorithm time is obviously $O(n)$.

StackExchange Computer Science Q#112728, answer score: 5