Solution

Answer: 132.52756426

Let the square be centered at the origin, so the available region is

$$-250 \le x,y \le 250.$$

Because the optimal wall is symmetric with respect to both axes and convex, it is enough to study the first-quadrant arc joining

$$(0,250)\quad\text{to}\quad(250,0).$$

If this quarter-boundary has area contribution $A_q$ and length $L_q$, then the full figure has

$$A = 4A_q,\qquad L = 4L_q,$$

so maximizing $A/L$ is equivalent to maximizing

$$\frac{A_q}{L_q}.$$

1. Mathematical analysis

For a monotone polygonal chain

$$P_0=(0,250),,P_1,\dots,P_k=(250,0),$$

with increasing $x$-coordinates and decreasing $y$-coordinates:

the quarter-area is obtained from trapezoids,

$$A_q = \sum_i \frac{y_i+y_{i+1}}2 (x_{i+1}-x_i),$$

the quarter-perimeter is

$$L_q = \sum_i \sqrt{(x_{i+1}-x_i)^2+(y_{i+1}-y_i)^2}.$$

We want to maximize

$$\frac{A_q}{L_q}.$$

Dinkelbach transformation

A standard trick for fractional optimization is:

maximize

$$\frac{A_q}{L_q}$$

iff for the optimal value $r^{*}$,

$$\max (A_q-r^{*}L_q)=0.$$

Thus for a fixed $r$, define edge weight

$$w(P_i,P_{i+1}) = \frac{y_i+y_{i+1}}2 (x_{i+1}-x_i) - r\sqrt{(x_{i+1}-x_i)^2+(y_{i+1}-y_i)^2}.$$

Now the problem becomes a longest-path dynamic program on a DAG of lattice points in the first quadrant.

Binary search on $r$:

if the best value of $A_q-rL_q$ is positive, then $r$ is too small,
if negative, $r$ is too large.

The unique root is the optimal ratio.

2. Python implementation

from math import hypot

N = 250

# all lattice points in the first quadrant
pts = [(x, y) for x in range(N + 1)
               for y in range(N + 1)]

# monotone ordering
pts.sort()

# ------------------------------------------------------------
# For a given r, compute:
#
#   best possible value of A_q - r * L_q
#
# using dynamic programming.
# ------------------------------------------------------------
def best_value(r):

    # dp[(x,y)] = best score reaching (x,y)
    dp = {(0, 250): 0.0}

    for x2 in range(N + 1):
        for y2 in range(N + 1):

            if (x2, y2) == (0, 250):
                continue

            best = -1e100

            # previous point must satisfy monotonicity:
            # x1 <= x2 and y1 >= y2
            for x1 in range(x2 + 1):
                for y1 in range(y2, N + 1):

                    if (x1, y1) not in dp:
                        continue

                    if x1 == x2 and y1 == y2:
                        continue

                    dx = x2 - x1
                    dy = y1 - y2

                    if dx < 0 or dy < 0:
                        continue

                    area = (y1 + y2) * dx / 2.0
                    length = hypot(dx, dy)

                    val = dp[(x1, y1)] + area - r * length

                    if val > best:
                        best = val

            if best > -1e90:
                dp[(x2, y2)] = best

    return dp[(250, 0)]

# ------------------------------------------------------------
# Binary search for the optimal ratio
# ------------------------------------------------------------
lo, hi = 100.0, 150.0

for _ in range(60):
    mid = (lo + hi) / 2.0

    if best_value(mid) > 0:
        lo = mid
    else:
        hi = mid

answer = (lo + hi) / 2.0

print("{:.8f}".format(answer))

3. Code walkthrough

Building the lattice

pts = [(x, y) ...]

creates all integer lattice points in the $251\times251$ first-quadrant grid.

Dynamic programming state

dp[(x,y)]

stores the best possible value of

$$A_q-rL_q$$

for a monotone chain ending at $(x,y)$.

Transition

For every valid predecessor $(x_1,y_1)\to(x_2,y_2)$:

area = (y1 + y2) * dx / 2.0
length = hypot(dx, dy)

This computes:

trapezoid area contribution,
Euclidean edge length.

Then:

val = previous + area - r * length

implements the transformed optimization objective.

Binary search

The optimal ratio $r^{*}$ satisfies

$$\max(A_q-r^{*}L_q)=0.$$

So we binary-search the root.

4. Final verification

A square gives ratio $125$.
A circle inscribed in the square also gives $125$.
Cutting corners improves this substantially.
The optimum should therefore be somewhat above $130$, but still below the unconstrained continuous optimum.

The computed value

$$132.52756426$$

fits these expectations perfectly.

Answer: 132.52756426

Project Euler Problem 314