We have an infinitely planar cartesian coordinate system on which $N$ points are plotted. Cartesian coordinates of the point $i$ are represented by $(X_i,Y_i)$. Now we want to draw $(N−1)$ line segments which may have arbitrary lengths and the points may or may not lie on these lines. The slope of each line must be $1$ or $−1$.
Let's denote the minimum distance we have to walk from a point $i$ to reach a line by $D_i$ and let's say $a=\max(D_1,D_2,D_3,...,D_N)$. We want this distance to be minimum as possible.
Thus we have to plot lines in such a way that it minimizes $a$ and compute $a \sqrt2$.
Devise an optimal procedure to find $a$ and thus compute $a \sqrt2$.
My understanding is as the slopes are $1$ or $-1$ the equations of the lines would be $y = x + c$ or $y = -x + c$ and we just have to find the y-intercept $c$ which minimizes the distance 'a' in the problem. Also, the minimum distance from a point to the line is the length of the perpendicular to the line. So I am having difficulty to devise an algorithm which will check all possible values of $'c'$ and find the optimal one.