From $O, A_{1}, A_{2016}$ are collinear, there exists some positive number $k$ such that
$$\frac{x_{1}}{y_{1}} = \frac{x_{2016}}{y_{2016}} = k > 0.$$
We shall prove that for all $i = \overline{2,2015}$, $\frac{x_{i}}{y_{i}} > k$. Indeed,
Notice that
$$x_{n+1} = \sqrt{\frac{x_{n}^{2} + x_{n+2}^{2}}{2}} \Leftrightarrow x_{n+1}^{2} = \frac{x_{n}^{2} + x_{n+2}^{2}}{2},$$
which implies that $(x_{n}^{2})$ forms an arithmetic sequence.
Hence, for all $i = \overline{2,2015}$, let
$$\alpha_{i} = \frac{2016 - i}{2015}, \quad \beta_{i} = \frac{i - 1}{2015}$$
then $\alpha_{i} + \beta_{i} = 1$, $2 \leq i \leq 2015$ and
$$x_{i}^{2} = \alpha_{i} x_{1}^{2} + \beta_{i} x_{2016}^{2} \Leftrightarrow x_{i} = \sqrt{\alpha_{i} x_{1}^{2} + \beta_{i} x_{2016}^{2}}.$$
Similarly, we also have
$$y_{i} = \left(\alpha_{i} \sqrt{y_{1}} + \beta_{i} \sqrt{y_{2016}}\right)^{2} \text{ and } k y_{i} = \left(\alpha_{i} \sqrt{x_{1}} + \beta_{i} \sqrt{x_{2016}}\right)^{2}.$$
We need to prove
$$\sqrt{\alpha_{i} x_{1}^{2} + \beta_{i} x_{2016}^{2}} > \left(\alpha_{i} \sqrt{x_{1}} + \beta_{i} \sqrt{x_{2016}}\right)^{2}$$
for all $2 \leq i \leq 2015$ $(*)$.
By applying the Cauchy-Schwarz inequality, we have
$$\begin{aligned} (\alpha_{i} + \beta_{i}) (\alpha_{i} x_{1}^{2} + \beta_{i} x_{2016}^{2}) & \geq (\alpha_{i} x_{1} + \beta_{i} x_{2016})^{2} \\ & = \left((\alpha_{i} + \beta_{i})(\alpha_{i} x_{1} + \beta_{i} x_{2016})\right)^{2} \\ & \geq \left(\alpha_{i} \sqrt{x_{1}} + \beta_{i} \sqrt{x_{2016}}\right)^{4} \end{aligned}$$
So the inequality $(*)$ is true for each $2 \leq i \leq 2015$. Since all points are distinct, then $A_{1} \neq A_{2016} \Leftrightarrow x_{1} \neq x_{2016}$, so equality does not occur in $(*)$.
So all the points $A_{2}, A_{3}, \ldots, A_{2015}$ belong to the same side with respect to $d$.