Detailed mathematical approach

Problem Summary

Problem 966 asks for all integer-sided triangles with \(1 \le a \le b \le c\), \(a+b>c\), and \(a+b+c \le 200\). For each such triangle \(T\), we draw a circle whose area is exactly the area of \(T\), and we may place the circle center anywhere inside the triangle. The quantity for one triangle is

$I(a,b,c)=\max_{x\in T}\operatorname{area}\bigl(T\cap B(x,r)\bigr),\qquad r=\sqrt{\frac{A_T}{\pi}},$

where \(A_T\) is the triangle area and \(B(x,r)\) is the closed disk of radius \(r\) centered at \(x\). The final answer is the sum

$S=\sum_{\substack{1\le a\le b\le c\\ a+b>c\\ a+b+c\le 200}} I(a,b,c).$

The triangle count is finite but still large: there are exactly 57,222 admissible triples. The real work is therefore geometric. For each triangle, we need an exact formula for the overlap area at a fixed center, and then we need a robust numerical search for the best center.

Mathematical Approach

The implementations use a two-layer strategy. First, for any chosen center, they compute the triangle-disk intersection area exactly up to floating-point arithmetic. Second, they maximize that continuous function over the closed triangular region.

Reconstructing the triangle and the equal-area circle

The side lengths are sorted so that \(a \le b \le c\), then the longest side is placed on the x-axis:

$A=(0,0),\qquad B=(c,0),\qquad C=(x_C,y_C).$

The law of cosines gives

$x_C=\frac{b^2+c^2-a^2}{2c},\qquad y_C=\sqrt{b^2-x_C^2}.$

This produces a canonical copy of the triangle. Its area can be written either as a cross product or with Heron's formula:

$A_T=\frac12\bigl|\operatorname{cross}(B-A,C-A)\bigr|=\sqrt{s(s-a)(s-b)(s-c)},\qquad s=\frac{a+b+c}{2}.$

The circle is forced to have the same area, so its radius is

$r=\sqrt{\frac{A_T}{\pi}}.$

Once \(T\) and \(r\) are known, the remaining problem is purely positional: choose the center \(x\in T\) to maximize the overlap \(T\cap B(x,r)\).

Exact overlap area from oriented edge contributions

Fix a candidate center \(x\). Instead of moving the circle, translate the triangle by \(-x\), so the circle becomes the disk \(B(0,r)\). Now consider one directed edge with translated endpoints \(p\) and \(q\). Any interior intersection with the circle boundary satisfies

$\|p+t(q-p)\|^2=r^2,\qquad 0<t<1.$

This is a quadratic equation, so an edge has at most two interior intersection points. After splitting the edge at those points, every resulting subsegment lies entirely inside the disk or entirely outside it.

For a subsegment from \(u\) to \(v\), let \(m=(u+v)/2\). The contribution is

$C(u,v)= \begin{cases} \frac12\operatorname{cross}(u,v), & \|m\|^2\le r^2,\\[4pt] \frac12 r^2\operatorname{atan2}\!\bigl(\operatorname{cross}(u,v),\operatorname{dot}(u,v)\bigr), & \|m\|^2>r^2. \end{cases}$

The first line is the signed area of the triangle formed with the origin; the second is the signed area of the circular sector swept from \(u\) to \(v\). Summing these contributions over the three directed edges gives the exact overlap for the chosen center:

$I(a,b,c;x)=\left|\sum_{e\in\partial T} C_e\right|.$

Why midpoint classification is enough

Once all line-circle intersection points have been inserted, a subsegment cannot cross the circle boundary again. Because the disk is convex, that means the entire subsegment is either inside the disk or outside it, except possibly at boundary endpoints. The midpoint is therefore enough to decide which formula applies.

This is the crucial invariant in the area evaluator: every complicated-looking triangle-circle intersection is reduced to a short list of edge pieces, and each piece contributes by one of two closed forms. No rasterization, angular sampling, or numerical integration is needed.

Worked example: the \(3\)-\(4\)-\(5\) triangle

For \((a,b,c)=(3,4,5)\), the canonical coordinates are

$A=(0,0),\qquad B=(5,0),\qquad C=\left(\frac{16+25-9}{10},\sqrt{16-\left(\frac{32}{10}\right)^2}\right)=(3.2,2.4).$

The area is

$A_T=\frac12\cdot 5\cdot 2.4=6,$

so the equal-area circle radius is

$r=\sqrt{\frac{6}{\pi}}\approx 1.3819766.$

One of the search seeds is the incenter, which here is the side-length weighted point

$\frac{3A+4B+5C}{3+4+5}=(3,1).$

Running the exact overlap evaluator inside the optimizer produces the checkpoint value

$I(3,4,5)\approx 4.593049.$

The implementations also verify \(I(3,4,6)\approx 3.552564\), giving a second nontrivial numerical check.

Searching for the optimal center

The function \(x\mapsto I(a,b,c;x)\) is continuous, and the feasible region \(T\) is compact, so a maximum certainly exists. The implementations search for it numerically with a projected multi-start Nelder-Mead scheme.

The seed set is deliberately geometric rather than random: a barycentric grid with denominator \(5\) contributes 21 candidate centers, then the centroid and the incenter are added. All seeds are scored, the best four are used as starting simplices for a first Nelder-Mead phase, and the best result is refined once more with a smaller step size. Every trial point is projected back to the nearest point of the triangle, so feasibility is preserved automatically.

From one triangle to the global sum

After the per-triangle maximizer is available, the global answer is simply the sum over all admissible triples. The important point is that the expensive part is local but independent: each triangle can be processed on its own, and the exact overlap formula makes every function evaluation \(O(1)\).

How the Code Works

The C++, Python, and Java implementations first enumerate all triples with \(1\le a\le b\le c\), triangle inequality, and perimeter at most \(200\). For each triple they sort the sides, build the canonical coordinates on the x-axis, compute the area, the equal-area radius, and the longest side length used to scale the search steps.

For a fixed candidate center, the implementation translates the triangle so the disk is centered at the origin. Each of the three edges is intersected with the circle by solving the quadratic equation above, then broken into subsegments. Every subsegment contributes either a cross-product term or a sector-angle term, and the absolute value of the oriented sum is the overlap area. Because the evaluator is analytic, the optimizer works with exact geometry rather than with a discretized picture.

The search phase evaluates 23 seed points, keeps the four best, runs a projected Nelder-Mead search from each of them, then performs one smaller refinement around the current winner. The implementations clamp the final value to the interval \([0,A_T]\) to guard against tiny floating overshoots. The C++ path distributes triangles across worker threads and uses compensated summation in both the thread-local totals and the final reduction; the Java path uses parallel reduction. The final total is rounded to two decimal places.

Complexity Analysis

There are exactly 57,222 admissible triangles. For one triangle, a single overlap evaluation is constant-time: there are only three edges, each edge generates at most two interior circle intersections, and the resulting contribution list is bounded in size. The search budget is also fixed: 23 seed evaluations, up to four first-stage Nelder-Mead runs of 90 iterations each, and one final refinement of 50 iterations. Consequently the total runtime is effectively linear in the number of triangles, with a moderate constant factor.

Memory usage is \(O(1)\) per worker beyond the current triangle and a small set of partial sums. The main numerical risk is cancellation during the final accumulation, which is why the C++ implementation uses Kahan-style compensated summation for the grand total.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=966
2. Heron's formula: Wikipedia - Heron's formula
3. Law of cosines: Wikipedia - Law of cosines
4. Circle-line intersection: MathWorld - Circle-Line Intersection
5. Circular sector: Wikipedia - Circular sector
6. Nelder-Mead method: Wikipedia - Nelder-Mead method
7. Kahan summation algorithm: Wikipedia - Kahan summation algorithm