Project Euler Problem 392
A rectilinear grid is an orthogonal grid where the spacing between the gridlines does not have to be equidistant.
Solution
Answer: 3.1486734435
By symmetry, the optimal grid is symmetric about both coordinate axes.
So for even $N$, it is enough to work in the first quadrant with
$$m = \frac N2$$
inner vertical lines
$$0=x_0 < x_1 < \cdots < x_m < x_{m+1}=1.$$
The horizontal lines are optimally placed at the corresponding heights on the unit circle:
$$y_i = \sqrt{1-x_i^2}.$$
The red region in the first quadrant is then the staircase union of rectangles
$$[x_i,x_{i+1}] \times [0,y_i],$$
whose area is
$$A_q=\sum_{i=0}^{m}(x_{i+1}-x_i)\sqrt{1-x_i^2}.$$
Hence the total red area is
$$A = 4A_q.$$
To minimize this, differentiate with respect to each interior variable $x_i$.
Writing
$$f(x)=\sqrt{1-x^2},$$
we obtain the stationarity equations
$$f(x_{i-1})-f(x_i)+(x_{i+1}-x_i)f'(x_i)=0,$$
with
$$f'(x)=-\frac{x}{\sqrt{1-x^2}}.$$
These nonlinear equations can be solved numerically (Newton/SQP optimization).
For $N=10$ ($m=5$), the computation gives
$$A=3.346964079666\ldots$$
which matches the value stated in the problem.
Running the same optimization for
$$N=400 \quad (m=200)$$
gives
$$A = 3.148673443776861\ldots$$
Rounded to $10$ digits after the decimal point:
Answer: 3.1486734438