Detailed mathematical approach

Problem Summary

We study integer-coordinate triangles \(A,B,C\) whose vertices lie in the closed disk

$x^2+y^2\le r^2.$

Among all such triangles with area

$\Delta=\frac12,$

the task is to maximize the perimeter. If several triangles reach the same perimeter, the one with larger circumradius \(R\) is preferred, and the reported quantity is

$T(r)=\frac{R}{r}.$

The brute-force search space is enormous, so the solution rewrites the geometry in terms of a primitive base edge and a one-dimensional lattice family for the third vertex.

Mathematical Approach

Fix one candidate triangle and choose the side \(AB\) as the base. Write

$u=B-A=(a,b),\qquad w=C-A,\qquad L=|u|=\sqrt{a^2+b^2}.$

The implementations only keep configurations where the chosen base is the longest side, so

$|w|\le L,\qquad |u-w|\le L.$

Step 1: Convert the area condition into a determinant equation

For lattice points, the doubled area is the absolute determinant:

$2\Delta=|\det(u,w)|.$

Because \(\Delta=\frac12\), every admissible triangle satisfies

$|\det(u,w)|=1.$

If \(A=(x_A,y_A)\) and \(C=(x,y)\), then \(w=C-A\), so the same condition becomes

$a y-b x=a y_A-b x_A\pm1.$

This immediately forces \(\gcd(a,b)=1\); if \(a\) and \(b\) had a common factor \(g>1\), then the left-hand side would always be divisible by \(g\), so it could never equal \(\pm1\).

Step 2: Parameterize all admissible third vertices

Since \(\gcd(a,b)=1\), the linear Diophantine equation

$-b x+a y=1$

has an integer solution. If the required right-hand side is some integer \(k\), one particular point on the line is obtained by scaling that solution by \(k\). Every other integer point on the same line differs by a multiple of the base vector \(u\), so the full family is

$C(t)=C_0+t(a,b),\qquad t\in\mathbb{Z}.$

Thus, once \(A\), \(B\), and the sign choice \(\pm1\) are fixed, the third vertex can only move along one lattice line parallel to the base.

Step 3: Intersect the lattice line with the disk

Substituting \(C(t)=C_0+t u\) into the disk constraint gives

$|C_0+t u|^2\le r^2,$

which expands to the quadratic inequality

$L^2 t^2+2(C_0\cdot u)t+\bigl(|C_0|^2-r^2\bigr)\le0.$

The discriminant tells us whether that line meets the disk at all. When it does, the admissible integers form one contiguous interval

$t_{\min}\le t\le t_{\max}.$

The implementations compute those endpoints with exact integer floor and ceiling arithmetic, so the feasibility test does not depend on floating-point rounding.

Step 4: Express the two other sides through one integer dot product

Let

$q=u\cdot w.$

This is an integer because both vectors have integer coordinates. Lagrange's identity gives

$|u|^2|w|^2=(u\cdot w)^2+\det(u,w)^2=q^2+1,$

hence

$|w|=\frac{\sqrt{q^2+1}}{L}.$

For the third side, use \(u-w=B-C\). Then

$u\cdot(u-w)=L^2-q,\qquad \det(u,u-w)=\det(u,w),$

so

$|u-w|=\frac{\sqrt{(L^2-q)^2+1}}{L}.$

The perimeter therefore becomes

$P=L+\frac{\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1}}{L}.$

Step 5: Derive the pruning bound \(P\le2L+\frac1L\)

Because the chosen base must be the longest side, both \(q\) and \(L^2-q\) are positive integers. For every integer \(n\ge1\),

$\sqrt{n^2+1}\le n+\frac{1}{2n}.$

Apply this inequality once to \(q\) and once to \(L^2-q\):

$\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1} \le q+\frac{1}{2q}+(L^2-q)+\frac{1}{2(L^2-q)} \le L^2+1.$

After dividing by \(L\), we obtain

$|w|+|u-w|\le L+\frac1L,$

and therefore

$\boxed{P\le2L+\frac1L.}$

This is the key pruning inequality used by the search. Once even this optimistic upper bound drops below the best perimeter already found, no shorter base can improve the answer.

Step 6: Search edges by deficiency from the diameter

Any edge inside the disk has length at most \(2r\). For that reason, promising base edges are those with \(L\) very close to \(2r\). The implementations measure this gap by the deficiency

$d=4r^2-L^2.$

Small \(d\) means an almost diametral base, so candidate primitive edges are generated in increasing deficiency, or equivalently decreasing \(L\).

If the current best perimeter is \(P^*\), then a future edge can only win if

$2L+\frac1L>P^*.$

Solving the equality gives the larger root

$L_{\min}=\frac{P^*+\sqrt{(P^*)^2-8}}{4}.$

Hence no edge with \(L<L_{\min}\) can matter, and the search only needs to cover deficiencies up to

$d_{\max}=4r^2-L_{\min}^2.$

Worked Example

Take

$A=(0,0),\qquad B=(2,1).$

Then \(u=(2,1)\) and \(L^2=5\). The area condition becomes

$|\det(u,C-A)|=|2y-x|=1.$

Choose the \(+1\) branch. One integer point on the line \(2y-x=1\) is \((-1,0)\), so every solution has the form

$C(t)=(-1,0)+t(2,1).$

Inside the disk of radius \(3\), we need

$(-1+2t)^2+t^2\le9,$

which leaves \(t=0\) and \(t=1\). The choice \(t=1\) gives \(C=(1,1)\), and then

$|C-A|^2=2,\qquad |C-B|^2=1,\qquad P=\sqrt5+\sqrt2+1.$

Since \(\Delta=\frac12\), the circumradius is

$R=\frac{|AB|\cdot|AC|\cdot|BC|}{4\Delta} =\frac{\sqrt5\cdot\sqrt2\cdot1}{2} =\frac{\sqrt{10}}{2}.$

How the Code Works

The implementation first precomputes, for each integer \(x\in[-r,r]\), the largest \(|y|\) still inside the disk. That allows fast testing of whether both endpoints of a translated base edge stay inside the circle.

Next it builds primitive edge vectors \((a,b)\) with \(1\le b\le a\), so rotational and reflection symmetries are not revisited. Only vectors whose squared length lies in the current deficiency window are kept, and they are processed from longer to shorter edges.

For each admissible translation of the base, the C++, Python, and Java implementations examine the two determinant lines corresponding to area \(+\frac12\) and \(-\frac12\). An integer point on the chosen line is produced with the extended Euclidean algorithm, then shifted along the base direction so the quadratic disk test stays numerically small and exact.

Every integer point in the resulting \(t\)-interval is checked. The implementation discards cases where the third point coincides with an endpoint or where one of the other two sides exceeds the base length. Surviving candidates are compared first by perimeter and then, on ties, by circumradius.

The C++ version evaluates edge batches in parallel, the Java version mirrors the same exact search with arbitrary-precision arithmetic where needed, and the Python version acts as a thin bridge that launches the native computation and extracts the final numeric answer.

Complexity Analysis

Let \(E(D)\) be the number of primitive edge vectors whose deficiency is at most \(D\). Precomputing the disk boundary table costs \(O(r)\) time and \(O(r)\) memory. Generating and sorting the current candidate edges costs \(O(E(D)\log E(D))\).

For a single edge, the solver scans all translations that keep both endpoints in the disk; in the worst case this can be as large as \(O(r^2)\). Each valid translation yields at most two determinant lines, and each line contributes one contiguous interval of integer parameters for the third vertex. A deliberately loose bound for one search round is therefore \(O(r^2E(D))\), but in practice the deficiency window stays small, the perimeter bound removes many edges early, and the integer \(t\)-interval is usually short.

Overall, the method is strongly data-dependent but memory usage remains modest: \(O(r+E(D))\), plus thread-local state in the parallel C++ version.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=562
2. Pick's theorem: Wikipedia - Pick's theorem
3. Circumradius formulas: Wikipedia - Circumscribed circle
4. Extended Euclidean algorithm: Wikipedia - Extended Euclidean algorithm
5. Linear Diophantine equations: Wikipedia - Diophantine equation