Based on this CGCC challenge
My problem is: Imagine a cartesian plane wih squares each having a side length of 1 unit, And given the euclidian distance of two points on the plane which is $L$ units ($L ∈\mathbb{R^+}$), now calculate maximum number of squares a line segment with length of $L$ will touch (I mean intersect into the interior of a square).
Example for $L$ of $3$ and $5$:
The blue lines denote the line for maximum number of squares, which for 3 is 7 and 5 is 9 (Look closely)
Now this is the only way for me to solve the problem. Is there any nice formula that will take L and return the number of intersecting squares?
The solution is easier if we consider the $\Delta x$ and $\Delta y$ of the line. After that, we use $L=\sqrt{(\Delta x)^2+(\Delta y)^2}$ to tackle the original question. If we ignore cases where exact integers are involved, a (wlog. positiv) $\Delta x$ can lead to up to $\lceil \Delta x\rceil$ times that our line crosses a vertical line between grid squares. Similarly, we have $\lceil \Delta y\rceil$ times that we cross horizontally. In general position, no vertical step happens at the same time of a horizontal step (i.e., the line does not accidentally pass trough a lattice point. Thus our line passes through exactly $$n=1+\lceil \Delta x\rceil + \lceil \Delta y\rceil $$ grid squares.
But for what $\Delta x$ does $n$ become maximal? If we lower $\Delta x$ without changing th eceiling value, $\Delta y$ increases, and so possibly $\lceil\Delta y\rceil$ increases. Hence we will only consider $\Delta x= k+\epsilon$ with very small $\epsilon$. Question: When is $\Delta x'=(k\pm 1)+\epsilon$ better? The former makes (using that $\epsilon $ is small) $$\tag1 n=1+k+1+\left\lceil\sqrt{L^2-(k+\epsilon)^2}\,\right\rceil=k+2+\left\lceil\sqrt{L^2-k^2}\,\right\rceil,$$ and if we ignore the ceiling function, we have $$ \frac d{dk}n=1-\frac{k}{\sqrt{L^2-k^2}}$$ and we expect an extremum where this derivative vanishes, i.e., for $k\approx \sqrt{L^2-k^2}$, or: $$ \tag2k\approx \frac L{\sqrt 2}.$$ (In other words, the optimal line runs nearly at a $45^\circ $ angle (but slightly tilted so that its ends are very close to a grid line).
Example 1: If $L=3$, $(2)$ suggests $k\approx 2.12$, so we try out $k=2$ and perhaps $k=3$. With $k=2$, $(1)$ yields $$ n=2+2+\left\lceil\sqrt{9-4}\right\rceil=7$$ and with $k=3$, $$ n=3+2+\left\lceil\sqrt{9-9}\right\rceil=5,$$ so $n=7$ is the maximum.
Example 2: If $L=5$, $(2)$ suggests $k\approx 3.5$, so we try out $k=3$ and $k=4$. With $k=3$, $(1)$ yields $$ n=3+2+\left\lceil\sqrt{25-9}\right\rceil=9$$ and with $k=4$, $$ n=4+2+\left\lceil\sqrt{25-16}\right\rceil=9,$$ so at any rate, $n=9$ is the maximum.
Note that this method produced the correct result even though in the second example, $L^2-k^2$ was a perfect square. Indeed, all simplifications above are valid for that situation. In fact, problems (inaccuracies, off-by-one errors) will rather occur when $L$ is an integer multiple of $\sqrt 2$ - in which case the exact number of squares passed by a $45^\circ$ line is perhaps under debate anyway.