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.
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.
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)\).
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|.$$
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.
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.
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.
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)\).
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.
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.
Problem 966 betrachtet alle ganzzahligen Dreiecke mit \(1 \le a \le b \le c\), \(a+b>c\) und \(a+b+c \le 200\). Zu jedem solchen Dreieck \(T\) gehört ein Kreis mit derselben Fläche wie \(T\). Der Kreismittelpunkt darf irgendwo im Dreieck liegen. Für ein festes Dreieck ist also
$$I(a,b,c)=\max_{x\in T}\operatorname{area}\bigl(T\cap B(x,r)\bigr),\qquad r=\sqrt{\frac{A_T}{\pi}},$$
wobei \(A_T\) die Dreiecksfläche und \(B(x,r)\) die abgeschlossene Kreisscheibe mit Mittelpunkt \(x\) und Radius \(r\) ist. Gesucht wird die Gesamtsumme
$$S=\sum_{\substack{1\le a\le b\le c\\ a+b>c\\ a+b+c\le 200}} I(a,b,c).$$
Es gibt genau 57.222 zulässige Seiten-Tripel. Deshalb ist die Schwierigkeit nicht die Aufzählung der Dreiecke, sondern die präzise und stabile Auswertung des kontinuierlichen Maximums für jedes einzelne Dreieck.
Die Lösung kombiniert exakte Geometrie mit numerischer Optimierung. Für einen festen Mittelpunkt wird die Überlappungsfläche Dreieck-Scheibe exakt berechnet; anschließend wird diese Funktion auf dem abgeschlossenen Dreieck maximiert.
Zuerst werden die Seiten sortiert, also \(a \le b \le c\). Dann wird die längste Seite auf die x-Achse gelegt:
$$A=(0,0),\qquad B=(c,0),\qquad C=(x_C,y_C).$$
Aus dem Kosinussatz folgt
$$x_C=\frac{b^2+c^2-a^2}{2c},\qquad y_C=\sqrt{b^2-x_C^2}.$$
Damit ist das Dreieck eindeutig rekonstruiert. Seine Fläche lässt sich sowohl über das Kreuzprodukt als auch über die Heron-Formel schreiben:
$$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}.$$
Der Kreis soll dieselbe Fläche besitzen, also
$$r=\sqrt{\frac{A_T}{\pi}}.$$
Danach bleibt nur noch die Positionsfrage: Wo muss der Mittelpunkt \(x\in T\) liegen, damit \(\operatorname{area}(T\cap B(x,r))\) maximal wird?
Für einen gewählten Mittelpunkt \(x\) wird das Dreieck um \(-x\) verschoben. Dadurch liegt der Kreis im Ursprung als Scheibe \(B(0,r)\). Betrachte nun eine gerichtete Kante mit verschobenen Endpunkten \(p\) und \(q\). Innere Schnittpunkte mit dem Kreisrand erfüllen
$$\|p+t(q-p)\|^2=r^2,\qquad 0<t<1.$$
Das ist eine quadratische Gleichung, also kann eine Kante höchstens zwei innere Schnittpunkte besitzen. Nach dem Auftrennen an diesen Punkten liegt jedes Teilstück vollständig innerhalb oder vollständig außerhalb der Scheibe.
Für ein Teilstück von \(u\) nach \(v\) mit Mittelpunkt \(m=(u+v)/2\) gilt
$$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}$$
Der erste Fall ist eine orientierte Polygonfläche, der zweite Fall eine orientierte Kreissektorfläche. Die exakte Überlappung für den Mittelpunkt \(x\) ist dann
$$I(a,b,c;x)=\left|\sum_{e\in\partial T} C_e\right|.$$
Nach dem Einfügen aller Kreis-Schnittpunkte kann ein Teilsegment den Kreisrand nicht noch einmal kreuzen. Wegen der Konvexität der Scheibe liegt das gesamte Teilsegment also entweder innen oder außen, abgesehen von Randpunkten. Deshalb genügt ein Blick auf den Mittelpunkt, um die richtige geschlossene Formel auszuwählen.
Genau das macht den Flächenauswerter effizient: Aus einer scheinbar komplizierten Dreieck-Kreis-Geometrie wird eine kleine Liste von Kantenstücken, und jedes dieser Stücke liefert sofort einen expliziten Beitrag. Es gibt also weder Rasterung noch numerische Flächenintegration.
Für \((a,b,c)=(3,4,5)\) erhält man die kanonischen Koordinaten
$$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).$$
Die Fläche ist
$$A_T=\frac12\cdot 5\cdot 2.4=6,$$
also hat der flächengleiche Kreis den Radius
$$r=\sqrt{\frac{6}{\pi}}\approx 1.3819766.$$
Einer der Startpunkte der Optimierung ist der Inkreismittelpunkt, hier der seitengewichtete Punkt
$$\frac{3A+4B+5C}{3+4+5}=(3,1).$$
Mit dem exakten Flächenauswerter und der anschließenden Optimierung entsteht der Kontrollwert
$$I(3,4,5)\approx 4.593049.$$
Außerdem prüfen die Implementierungen \(I(3,4,6)\approx 3.552564\). Beide Werte dienen als harte numerische Validierung.
Die Funktion \(x\mapsto I(a,b,c;x)\) ist stetig, und das zulässige Gebiet \(T\) ist kompakt. Ein Maximum existiert also sicher. Gesucht wird es numerisch mit einem projizierten Multi-Start-Nelder-Mead-Verfahren.
Die Startpunkte sind bewusst geometrisch gewählt: Ein baryzentrisches Gitter mit Nenner \(5\) liefert 21 Kandidaten, dazu kommen Schwerpunkt und Inkreismittelpunkt. Alle Startpunkte werden bewertet, die besten vier dienen als Ausgang für eine erste Nelder-Mead-Phase, und das beste Ergebnis wird danach mit kleinerer Schrittweite noch einmal verfeinert. Jeder Testpunkt wird auf den nächstgelegenen Punkt des Dreiecks projiziert, sodass die Nebenbedingung \(x\in T\) automatisch erfüllt bleibt.
Ist das Maximum für ein Dreieck gefunden, wird es einfach zur Gesamtsumme addiert. Die wesentliche Struktur ist Entkopplung: Jedes Dreieck wird unabhängig bearbeitet, und jede Funktionsauswertung kostet dank der expliziten Kantenformeln nur \(O(1)\).
Die C++-, Python- und Java-Implementierungen erzeugen zuerst alle Tripel mit \(1\le a\le b\le c\), Dreiecksungleichung und Umfang höchstens \(200\). Für jedes Tripel werden die Seiten sortiert, die kanonischen Koordinaten auf der x-Achse aufgebaut, die Fläche bestimmt, der Radius des flächengleichen Kreises berechnet und die längste Seite als Größenskala für die Optimierung gespeichert.
Für einen festen Mittelpunkt verschiebt die Implementierung das Dreieck so, dass die Scheibe im Ursprung liegt. Dann wird jede der drei Kanten mit dem Kreis geschnitten, an den Schnittparametern zerlegt und Teilstück für Teilstück ausgewertet. Je nach Mittelpunktslage des Teilstücks wird entweder ein Kreuzproduktterm oder ein Sektorterm addiert. Dadurch arbeitet der Optimierer mit exakter Geometrie statt mit einer diskretisierten Näherung.
In der Suchphase werden 23 Startpunkte ausgewertet, die besten vier ausgewählt, von dort projizierte Nelder-Mead-Läufe gestartet und anschließend eine kleinere Nachverfeinerung durchgeführt. Der Endwert wird vorsichtshalber auf das Intervall \([0,A_T]\) begrenzt. Der C++-Pfad verteilt die Dreiecke auf mehrere Threads und verwendet kompensierte Summation sowohl in den Thread-Teilsummen als auch in der Endreduktion; der Java-Pfad nutzt eine parallele Reduktion. Am Ende wird auf zwei Nachkommastellen gerundet.
Es gibt genau 57.222 zulässige Dreiecke. Für ein einzelnes Dreieck ist eine Überlappungsauswertung konstant teuer: Es gibt nur drei Kanten, jede Kante erzeugt höchstens zwei innere Kreis-Schnittpunkte, und damit bleibt auch die Anzahl der Teilstücke beschränkt. Zusätzlich ist das Optimierungsbudget fest vorgegeben: 23 Startwertungen, höchstens vier erste Nelder-Mead-Läufe mit je 90 Iterationen und eine Schlussverfeinerung mit 50 Iterationen. Die Gesamtlaufzeit ist damit praktisch linear in der Anzahl der Dreiecke.
Der Speicherbedarf ist \(O(1)\) pro Worker zusätzlich zum aktuell bearbeiteten Dreieck und zu wenigen Teilsummen. Die wichtigste numerische Gefahr ist Auslöschung beim Aufsummieren vieler Fließkommazahlen; deshalb verwendet die C++-Implementierung Kahan-artige kompensierte Summation für die Gesamtreduktion.
Problem 966, \(1 \le a \le b \le c\), \(a+b>c\) ve \(a+b+c \le 200\) koşullarını sağlayan tüm tam kenarlı üçgenleri inceler. Her üçgen \(T\) için, alanı tam olarak \(T\)'nin alanına eşit olan bir çember alıyoruz ve çember merkezini üçgenin içinde istediğimiz yere yerleştirebiliyoruz. Tek bir üçgen için hesaplanan büyüklük
$$I(a,b,c)=\max_{x\in T}\operatorname{area}\bigl(T\cap B(x,r)\bigr),\qquad r=\sqrt{\frac{A_T}{\pi}},$$
şeklindedir. Burada \(A_T\) üçgen alanını, \(B(x,r)\) ise merkezi \(x\) olan kapalı diski gösterir. Sonuçta toplanan değer
$$S=\sum_{\substack{1\le a\le b\le c\\ a+b>c\\ a+b+c\le 200}} I(a,b,c)$$
olur. Uygun üçgen sayısı 57.222 olduğundan, asıl zorluk üçgenleri üretmek değil; her üçgen için sürekli bir maksimumu güvenilir biçimde hesaplamaktır.
Çözüm iki katmanlıdır. Önce, merkez sabitken üçgen ile disk kesişiminin alanı analitik olarak hesaplanır. Sonra bu sürekli fonksiyon, kapalı üçgen bölgesi üzerinde sayısal olarak maksimize edilir.
Kenarlar önce \(a \le b \le c\) olacak biçimde sıralanır, ardından en uzun kenar x-eksenine yerleştirilir:
$$A=(0,0),\qquad B=(c,0),\qquad C=(x_C,y_C).$$
Kosinüs teoreminden
$$x_C=\frac{b^2+c^2-a^2}{2c},\qquad y_C=\sqrt{b^2-x_C^2}$$
elde edilir. Böylece üçgenin kanonik koordinatları kurulmuş olur. Alan hem vektörel çapraz çarpımla hem de Heron formülüyle yazılabilir:
$$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}.$$
Çemberin alanı bununla aynı olmak zorunda olduğu için yarıçap
$$r=\sqrt{\frac{A_T}{\pi}}$$
olur. Bundan sonra problem tamamen konumsaldır: \(x\in T\) olacak şekilde merkezi seçip \(T\cap B(x,r)\) alanını büyütmek gerekir.
Bir aday merkez \(x\) sabitlendiğinde, çemberi taşımak yerine üçgen \(-x\) kadar ötelenir; böylece çember \(B(0,r)\) olur. Şimdi ötelenmiş uçları \(p\) ve \(q\) olan yönlü bir kenara bakalım. Çember sınırıyla olan iç kesişimler
$$\|p+t(q-p)\|^2=r^2,\qquad 0<t<1$$
denklemini sağlar. Bu denklem ikinci derecedendir; dolayısıyla bir kenarın en fazla iki iç kesişim noktası vardır. Bu noktalarda bölündükten sonra her alt parça tamamen diskin içinde ya da tamamen dışında kalır.
\(u\) ile \(v\) uçlarına sahip bir alt parça ve onun orta noktası \(m=(u+v)/2\) için katkı
$$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}$$
şeklindedir. İlk satır orijine göre yönlü üçgen alanını, ikinci satır ise yönlü dairesel sektör alanını verir. Üç yönlü kenarın toplamının mutlak değeri, seçilen merkez için tam örtüşme alanıdır:
$$I(a,b,c;x)=\left|\sum_{e\in\partial T} C_e\right|.$$
Tüm doğru-çember kesişimleri eklendikten sonra bir alt parça çember sınırını yeniden kesemez. Disk konveks olduğu için bu alt parçanın tamamı sınır uçları dışında ya içeridedir ya dışarıdadır. Bu nedenle hangi kapalı formülün kullanılacağını belirlemek için yalnızca orta noktaya bakmak yeterlidir.
Bu fikir alan hesaplayıcının temel değişmezidir. Karmaşık görünen üçgen-çember kesişimi, kısa bir alt kenar listesine indirgenir ve her alt kenar iki formülden biriyle anında değerlendirilir. Piksel tabanlı örnekleme ya da sayısal integrasyon gerekmez.
\((a,b,c)=(3,4,5)\) için kanonik koordinatlar
$$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)$$
olur. Alan
$$A_T=\frac12\cdot 5\cdot 2.4=6$$
ve eş-alanlı çemberin yarıçapı
$$r=\sqrt{\frac{6}{\pi}}\approx 1.3819766$$
çıkar. Arama tohumlarından biri, burada
$$\frac{3A+4B+5C}{3+4+5}=(3,1)$$
olan içteğet merkezi, yani kenar uzunluklarıyla ağırlıklandırılmış noktadır. Tam alan hesaplayıcısı optimizasyonun içinde çalıştırıldığında doğrulama değeri
$$I(3,4,5)\approx 4.593049$$
elde edilir. Uygulamalar ayrıca \(I(3,4,6)\approx 3.552564\) değerini de kontrol eder.
\(x\mapsto I(a,b,c;x)\) fonksiyonu süreklidir ve uygun bölge \(T\) kompakt olduğundan maksimum mutlaka vardır. Kod, bu maksimumu projeksiyonlu çoklu başlangıçlı Nelder-Mead ile bulur.
Başlangıç kümesi rastgele değil, geometriktir: paydası \(5\) olan bir baryentrik ızgara 21 aday üretir; bunlara ağırlık merkezi ve içteğet merkezi eklenir. Tüm tohumlar puanlanır, en iyi dört tanesi ilk Nelder-Mead aşaması için başlangıç olur ve çıkan en iyi nokta daha küçük bir adım boyuyla bir kez daha rafine edilir. Her deneme noktası üçgen üzerindeki en yakın noktaya projekte edildiği için uygunluk koşulu otomatik korunur.
Bir üçgen için maksimum bulunduğunda, küresel toplam yalnızca bu değerlerin toplanmasından ibarettir. Kritik nokta bağımsızlıktır: her üçgen tek başına işlenebilir ve açık kenar formülleri sayesinde her amaç fonksiyonu değerlendirmesi \(O(1)\) maliyetlidir.
C++, Python ve Java uygulamaları önce \(1\le a\le b\le c\), üçgen eşitsizliği ve çevre üst sınırı \(200\) koşullarını sağlayan tüm üçlüleri üretir. Her üçlü için kenarlar sıralanır, x-ekseni üzerinde kanonik koordinatlar kurulur, alan ve eş-alanlı çember yarıçapı hesaplanır, ayrıca optimizasyon adımlarını ölçeklemek için en uzun kenar saklanır.
Sabit bir merkez verildiğinde uygulama üçgeni, diskin merkezi orijinde olacak şekilde öteleyip üç kenarın her biri için doğru-çember kesişim parametrelerini çözer. Kesişimlerde bölünen alt parçalar orta nokta sınıflandırmasıyla değerlendirilir; içerideki parçalar çapraz çarpım terimi, dışarıdaki parçalar sektör açısı terimi üretir. Böylece optimizasyon pikselleştirilmiş bir yaklaşık alanla değil, doğrudan analitik bir alan hesaplayıcısıyla çalışır.
Arama aşaması 23 tohumu değerlendirir, en iyi dördünü seçer, her biri için projeksiyonlu Nelder-Mead çalıştırır ve kazananı daha küçük bir adımla son kez rafine eder. Son değer küçük kayan nokta sapmalarına karşı \([0,A_T]\) aralığına kırpılır. C++ yolu üçgenleri iş parçacıklarına dağıtır ve hem yerel hem de genel toplamda telafili toplama kullanır; Java yolu paralel indirgeme yapar. Sonuç iki ondalık basamağa yuvarlanır.
Uygun üçgen sayısı tam olarak 57.222'dir. Tek bir üçgen için bir örtüşme değerlendirmesi sabit zamanlıdır: yalnızca üç kenar vardır, her kenarın en fazla iki iç çember kesişimi oluşur ve dolayısıyla alt parça sayısı da sınırlıdır. Arama bütçesi de sabittir: 23 tohum değerlendirmesi, en fazla dört adet 90 iterasyonlu ilk faz Nelder-Mead koşusu ve 50 iterasyonlu bir son rafine etme. Bu yüzden toplam çalışma süresi pratikte üçgen sayısına lineer davranır.
Bellek kullanımı, işçi başına mevcut üçgen ve birkaç kısmi toplam dışında \(O(1)\) düzeyindedir. En hassas sayısal nokta, çok sayıda kayan nokta değerinin toplanması sırasında oluşan iptaldir; bu nedenle C++ uygulaması toplamı Kahan tarzı telafili toplamayla biriktirir.
El problema 966 recorre todos los triángulos de lados enteros con \(1 \le a \le b \le c\), \(a+b>c\) y \(a+b+c \le 200\). Para cada triángulo \(T\) se considera un círculo cuya área es exactamente la misma que la de \(T\), y el centro del círculo puede colocarse en cualquier punto interior del triángulo. Para un triángulo fijo se define
$$I(a,b,c)=\max_{x\in T}\operatorname{area}\bigl(T\cap B(x,r)\bigr),\qquad r=\sqrt{\frac{A_T}{\pi}},$$
donde \(A_T\) es el área del triángulo y \(B(x,r)\) es el disco cerrado de radio \(r\) centrado en \(x\). La cantidad final es
$$S=\sum_{\substack{1\le a\le b\le c\\ a+b>c\\ a+b+c\le 200}} I(a,b,c).$$
Hay exactamente 57.222 ternas admisibles. Por eso el reto real no es enumerarlas, sino resolver con precisión una maximización continua para cada una.
La estrategia tiene dos partes. Primero se calcula con geometría exacta el área de intersección entre el triángulo y el disco para un centro dado. Después se maximiza esa función continua sobre la región triangular cerrada.
Se ordenan los lados para que \(a \le b \le c\) y se coloca el lado mayor sobre el eje x:
$$A=(0,0),\qquad B=(c,0),\qquad C=(x_C,y_C).$$
Por la ley de cosenos,
$$x_C=\frac{b^2+c^2-a^2}{2c},\qquad y_C=\sqrt{b^2-x_C^2}.$$
Asi queda una copia canónica del triángulo. Su área puede escribirse mediante producto cruzado o con la fórmula de Herón:
$$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}.$$
El círculo debe tener la misma área, de modo que
$$r=\sqrt{\frac{A_T}{\pi}}.$$
Una vez fijados \(T\) y \(r\), el problema pasa a ser: elegir \(x\in T\) para maximizar \(\operatorname{area}(T\cap B(x,r))\).
Para un centro candidato \(x\), en vez de mover el círculo se traslada el triángulo por \(-x\), con lo cual el círculo queda como el disco \(B(0,r)\). Considérese una arista orientada con extremos trasladados \(p\) y \(q\). Los puntos interiores de intersección con la circunferencia cumplen
$$\|p+t(q-p)\|^2=r^2,\qquad 0<t<1.$$
Es una ecuación cuadrática, así que cada arista tiene a lo sumo dos intersecciones interiores. Al cortar en esos puntos, cada subsegmento queda completamente dentro o completamente fuera del disco.
Para un subsegmento con extremos \(u\) y \(v\), y punto medio \(m=(u+v)/2\), la contribución es
$$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}$$
La primera fórmula es un área triangular orientada; la segunda, un sector circular orientado. Sumando sobre las tres aristas orientadas se obtiene el área exacta para ese centro:
$$I(a,b,c;x)=\left|\sum_{e\in\partial T} C_e\right|.$$
Después de insertar todas las intersecciones recta-círculo, un subsegmento ya no puede volver a cruzar la frontera del disco. Como el disco es convexo, todo el subsegmento queda dentro o fuera salvo quizá en los extremos. Por eso el punto medio basta para decidir cuál de las dos fórmulas cerradas debe usarse.
Ese es el invariante clave del evaluador geométrico. Una intersección triángulo-círculo aparentemente complicada se reduce a unas pocas piezas de borde, y cada pieza aporta un término explícito. No hace falta mallado, muestreo angular ni integración numérica.
Para \((a,b,c)=(3,4,5)\), las coordenadas canónicas son
$$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).$$
El área vale
$$A_T=\frac12\cdot 5\cdot 2.4=6,$$
así que el radio del círculo de igual área es
$$r=\sqrt{\frac{6}{\pi}}\approx 1.3819766.$$
Una de las semillas de búsqueda es el incentro, que en este caso coincide con el punto ponderado por longitudes
$$\frac{3A+4B+5C}{3+4+5}=(3,1).$$
Al ejecutar el evaluador exacto dentro del optimizador aparece el valor de control
$$I(3,4,5)\approx 4.593049.$$
Las implementaciones también verifican \(I(3,4,6)\approx 3.552564\), lo que sirve como segunda comprobación numérica fuerte.
La función \(x\mapsto I(a,b,c;x)\) es continua y la región factible \(T\) es compacta, así que el máximo existe. El cálculo lo busca numéricamente con un esquema Nelder-Mead multiarranque con proyección.
Las semillas no son aleatorias. Una malla baricéntrica con denominador \(5\) aporta 21 centros candidatos, y luego se añaden el baricentro y el incentro. Se evalúan todas, se conservan las cuatro mejores para una primera fase de Nelder-Mead y después el mejor resultado se refina una vez más con un paso menor. Cada punto de prueba se proyecta al punto más cercano del triángulo, de modo que la restricción \(x\in T\) siempre se cumple.
Cuando ya se tiene el máximo de un triángulo, la respuesta global es simplemente la suma de todos esos máximos. La ventaja estructural es que cada triángulo es independiente y cada evaluación del objetivo cuesta \(O(1)\) gracias a la fórmula exacta basada en aristas.
Las implementaciones en C++, Python y Java enumeran primero todas las ternas con \(1\le a\le b\le c\), desigualdad triangular y perímetro no mayor que \(200\). Para cada terna ordenan los lados, construyen las coordenadas canónicas sobre el eje x, calculan el área, el radio del círculo de igual área y la longitud máxima usada para escalar los pasos del optimizador.
Para un centro fijo, la implementación traslada el triángulo para que el disco quede centrado en el origen. Luego corta cada una de las tres aristas en los parámetros de intersección con el círculo y evalúa cada subtramo. Los tramos interiores aportan un término de producto cruzado y los exteriores un término de sector circular. Eso permite que la optimización trabaje con un evaluador analítico, no con una aproximación por muestreo.
La fase de búsqueda evalúa 23 semillas, toma las cuatro mejores, ejecuta Nelder-Mead proyectado desde cada una y aplica una refinación final más pequeña alrededor del mejor punto encontrado. El valor final se recorta al intervalo \([0,A_T]\) para evitar pequeños excesos numéricos. La ruta en C++ reparte los triángulos entre varios hilos y usa suma compensada en la reducción; la ruta en Java usa reducción paralela. El total final se redondea a dos decimales.
Hay exactamente 57.222 triángulos admisibles. Para un triángulo dado, una evaluación del solapamiento es de tiempo constante: solo hay tres aristas, cada arista produce como máximo dos intersecciones interiores con la circunferencia y por tanto un número acotado de subsegmentos. Además, el presupuesto de búsqueda es fijo: 23 evaluaciones iniciales, hasta cuatro ejecuciones de 90 iteraciones y una refinación final de 50 iteraciones. En consecuencia, el tiempo total es esencialmente lineal en el número de triángulos.
El uso de memoria es \(O(1)\) por trabajador, aparte del triángulo actual y unas pocas sumas parciales. El principal riesgo numérico es la cancelación al acumular muchos valores en coma flotante; por eso la implementación en C++ usa suma compensada al construir el total.
第 966 题枚举所有满足 \(1 \le a \le b \le c\)、\(a+b>c\)、\(a+b+c \le 200\) 的整边三角形。对每个三角形 \(T\)，取一个面积与 \(T\) 完全相同的圆，并允许圆心放在三角形内部任意位置。单个三角形对应的量定义为
$$I(a,b,c)=\max_{x\in T}\operatorname{area}\bigl(T\cap B(x,r)\bigr),\qquad r=\sqrt{\frac{A_T}{\pi}},$$
其中 \(A_T\) 是三角形面积，\(B(x,r)\) 是以 \(x\) 为圆心、半径为 \(r\) 的闭圆盘。最终要求的是
$$S=\sum_{\substack{1\le a\le b\le c\\ a+b>c\\ a+b+c\le 200}} I(a,b,c).$$
满足条件的边长三元组一共有 57,222 个，因此难点并不在枚举，而在于如何对每个三角形高精度地求一个连续优化问题的最大值。
整体方法分成两层。第一层是在圆心固定时，精确计算三角形与圆盘的交面积；第二层是在闭合三角形区域内，对这个连续函数做数值最大化。
先将边长排序为 \(a \le b \le c\)，再把最长边放在 x 轴上：
$$A=(0,0),\qquad B=(c,0),\qquad C=(x_C,y_C).$$
由余弦定理可得
$$x_C=\frac{b^2+c^2-a^2}{2c},\qquad y_C=\sqrt{b^2-x_C^2}.$$
这样就得到三角形的标准坐标表示。面积既可以写成叉积形式，也可以写成海伦公式：
$$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}.$$
由于圆的面积必须与三角形相同，所以半径为
$$r=\sqrt{\frac{A_T}{\pi}}.$$
到这一步以后，问题就转化成了纯位置问题：在 \(x\in T\) 的约束下，怎样选圆心才能使 \(T\cap B(x,r)\) 的面积最大。
固定一个候选圆心 \(x\) 后，不去移动圆，而是把三角形整体平移 \(-x\)，这样圆就变成了以原点为中心的圆盘 \(B(0,r)\)。考虑一条平移后的有向边，其端点为 \(p\) 和 \(q\)。边与圆的内部交点满足
$$\|p+t(q-p)\|^2=r^2,\qquad 0<t<1.$$
这是一个二次方程，所以一条边最多只有两个内部交点。把边在这些交点处分开后，每一小段都完全处于圆盘内部或外部。
对一段端点为 \(u,v\) 的小线段，记其中点 \(m=(u+v)/2\)。它的贡献是
$$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}$$
第一种情况是原点与线段形成的有向三角形面积，第二种情况是有向圆扇形面积。把三条有向边的贡献加总后取绝对值，就得到该圆心对应的精确交面积：
$$I(a,b,c;x)=\left|\sum_{e\in\partial T} C_e\right|.$$
因为所有直线与圆的交点都已经事先插入，所以任何一个小线段都不可能再次穿过圆边界。圆盘又是凸集，于是这段线要么整体在圆内，要么整体在圆外，只可能在端点碰到边界。这样一来，用中点判断属于哪种情形就足够了。
这是面积计算器最关键的不变量。原本复杂的三角形-圆交集边界，被拆成少量简单的边段，每一段都直接套用封闭公式即可。因此实现中完全不需要像素化、角度采样或数值积分。
当 \((a,b,c)=(3,4,5)\) 时，标准坐标为
$$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).$$
面积是
$$A_T=\frac12\cdot 5\cdot 2.4=6,$$
所以等面积圆的半径为
$$r=\sqrt{\frac{6}{\pi}}\approx 1.3819766.$$
搜索种子之一是内心，也就是按边长加权的点：
$$\frac{3A+4B+5C}{3+4+5}=(3,1).$$
在优化器内部调用精确面积计算器后，可以得到代码中的校验值
$$I(3,4,5)\approx 4.593049.$$
实现还会验证第二个检查点 \(I(3,4,6)\approx 3.552564\)，用来确认几何与优化过程都没有漂移。
函数 \(x\mapsto I(a,b,c;x)\) 连续，而可行域 \(T\) 是紧的，因此最大值必然存在。实现采用的是“投影 + 多起点”的 Nelder-Mead 搜索。
起点不是随机生成的，而是有几何意义的集合：分母为 \(5\) 的重心坐标网格提供 21 个候选点，再额外加入重心和内心。先对所有种子打分，取最好的四个作为第一阶段 Nelder-Mead 的起始单纯形，然后再用更小的步长对当前最优点做一次精修。每次生成新试探点后，都会把它投影回三角形上的最近点，因此始终满足 \(x\in T\)。
一旦某个三角形的最大重叠面积算出，整体答案就只是把所有三角形的结果相加。这里最重要的结构性质是独立性：每个三角形都可以单独处理，而每次目标函数求值由于只有常数规模的边分解，因此代价是 \(O(1)\)。
C++、Python 和 Java 实现都会先枚举所有满足 \(1\le a\le b\le c\)、三角形不等式成立且周长不超过 \(200\) 的三元组。对每个三元组，程序先排序边长，再建立放在 x 轴上的标准坐标，计算面积、等面积圆半径，以及用于设定搜索步长的最长边。
对固定圆心，程序把三角形平移到“圆心在原点”的坐标系里，然后分别处理三条边。每条边都通过求解上面的二次方程找到与圆的交参数，再被切成若干小段。内部小段贡献叉积项，外部小段贡献扇形项，最后取有向和的绝对值。这样优化器面对的是解析几何计算器，而不是离散近似。
搜索阶段先评估 23 个种子点，保留最好的 4 个，从这些起点分别做投影 Nelder-Mead，再对当前最优点做一次更小步长的精修。最终结果会被限制在 \([0,A_T]\) 区间内，以消除极小的浮点越界。C++ 路径把三角形分配给多个工作线程，并在局部求和与最终归并时都使用补偿求和；Java 路径则使用并行归约。最后总和按两位小数输出。
满足条件的三角形恰好有 57,222 个。对单个三角形而言，一次交面积求值是常数时间：只有 3 条边，每条边最多产生 2 个内部圆交点，因此小段数量有统一上界。搜索预算也是固定的：23 次初始评估、最多 4 次第一阶段 90 迭代 Nelder-Mead，以及 1 次 50 迭代的最终精修。所以总运行时间在实践中基本就是关于三角形数量的线性函数。
内存方面，除了当前处理的三角形和少量部分和以外，每个工作单元只需要 \(O(1)\) 额外空间。数值上最容易出问题的是大量浮点值相加时的抵消误差，因此 C++ 实现专门在总和归并中使用了 Kahan 风格的补偿求和。
Задача 966 перебирает все целочисленные треугольники, для которых \(1 \le a \le b \le c\), \(a+b>c\) и \(a+b+c \le 200\). Для каждого такого треугольника \(T\) берется круг той же площади, что и \(T\), а центр круга разрешено располагать в любой точке внутри треугольника. Для фиксированного треугольника рассматривается величина
$$I(a,b,c)=\max_{x\in T}\operatorname{area}\bigl(T\cap B(x,r)\bigr),\qquad r=\sqrt{\frac{A_T}{\pi}},$$
где \(A_T\) — площадь треугольника, а \(B(x,r)\) — замкнутый диск радиуса \(r\) с центром в точке \(x\). Итоговая сумма равна
$$S=\sum_{\substack{1\le a\le b\le c\\ a+b>c\\ a+b+c\le 200}} I(a,b,c).$$
Допустимых троек ровно 57 222, так что главная трудность не в переборе, а в точном вычислении непрерывного максимума для каждого треугольника.
Решение состоит из двух уровней. Сначала для фиксированного центра точно вычисляется площадь пересечения треугольника и диска. Затем эта непрерывная функция максимизируется на замкнутой треугольной области.
Стороны сортируются так, чтобы \(a \le b \le c\), после чего самая длинная сторона кладется на ось x:
$$A=(0,0),\qquad B=(c,0),\qquad C=(x_C,y_C).$$
Из закона косинусов получаем
$$x_C=\frac{b^2+c^2-a^2}{2c},\qquad y_C=\sqrt{b^2-x_C^2}.$$
Так строится каноническая копия треугольника. Его площадь можно записать через векторное произведение или по формуле Герона:
$$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}.$$
Так как круг должен иметь ту же площадь, его радиус равен
$$r=\sqrt{\frac{A_T}{\pi}}.$$
После этого задача становится позиционной: нужно выбрать центр \(x\in T\), чтобы площадь \(T\cap B(x,r)\) была максимальной.
Для выбранного центра \(x\) треугольник сдвигается на \(-x\), так что круг превращается в диск \(B(0,r)\). Рассмотрим ориентированное ребро с концами \(p\) и \(q\) после сдвига. Внутренние точки пересечения с окружностью удовлетворяют
$$\|p+t(q-p)\|^2=r^2,\qquad 0<t<1.$$
Это квадратное уравнение, поэтому у одного ребра не более двух внутренних точек пересечения. Если разрезать ребро в этих точках, каждый получившийся подотрезок целиком лежит либо внутри диска, либо вне его.
Для подотрезка с концами \(u\) и \(v\) и серединой \(m=(u+v)/2\) вклад равен
$$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}$$
Первая строка дает ориентированную площадь треугольника с вершиной в начале координат, вторая — ориентированную площадь кругового сектора. Сумма по трем ориентированным ребрам дает точную площадь для данного центра:
$$I(a,b,c;x)=\left|\sum_{e\in\partial T} C_e\right|.$$
После вставки всех точек пересечения прямая-окружность подотрезок больше не может снова пересечь границу круга. Поскольку диск выпуклый, весь подотрезок лежит внутри или вне диска, кроме, возможно, концов на границе. Поэтому середины достаточно, чтобы понять, какая из двух формул должна применяться.
Это и есть ключевой инвариант геометрического вычислителя. Сложное на вид пересечение треугольника с кругом распадается на небольшой набор граничных кусочков, и каждый из них сразу дает явный вклад. Никакой растеризации или численного интегрирования не требуется.
Для \((a,b,c)=(3,4,5)\) канонические координаты имеют вид
$$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).$$
Площадь равна
$$A_T=\frac12\cdot 5\cdot 2.4=6,$$
поэтому радиус круга равной площади равен
$$r=\sqrt{\frac{6}{\pi}}\approx 1.3819766.$$
Одним из стартовых центров является инцентр, то есть точка, взвешенная длинами сторон:
$$\frac{3A+4B+5C}{3+4+5}=(3,1).$$
Если запустить точный вычислитель площади внутри оптимизатора, получается контрольное значение
$$I(3,4,5)\approx 4.593049.$$
Кроме того, реализации проверяют еще одно значение: \(I(3,4,6)\approx 3.552564\).
Функция \(x\mapsto I(a,b,c;x)\) непрерывна, а допустимая область \(T\) компактна, значит максимум существует. Для его поиска используется многозапусковый Nelder-Mead с проекцией на треугольник.
Набор стартов геометрически осмыслен. Барицентрическая сетка с знаменателем \(5\) дает 21 кандидат, затем добавляются центроид и инцентр. Все точки оцениваются, четыре лучшие используются для первого этапа Nelder-Mead, а затем лучший найденный результат уточняется еще раз с меньшим шагом. Любая пробная точка проецируется в ближайшую точку треугольника, поэтому ограничение \(x\in T\) сохраняется автоматически.
После нахождения максимума для конкретного треугольника остается просто добавить его в общую сумму. Важное структурное свойство состоит в независимости: каждый треугольник обрабатывается отдельно, а одна оценка целевой функции стоит \(O(1)\) благодаря явной формуле по ребрам.
Реализации на C++, Python и Java сначала перечисляют все тройки с \(1\le a\le b\le c\), выполненной неравенством треугольника и периметром не больше \(200\). Для каждой тройки стороны сортируются, строятся канонические координаты на оси x, вычисляются площадь, радиус круга равной площади и максимальная сторона как масштаб для шага оптимизации.
Для фиксированного центра реализация сдвигает треугольник так, чтобы диск оказался в начале координат. Затем каждая из трех сторон пересекается с окружностью путем решения квадратного уравнения по параметру, после чего сторона режется на подотрезки. Внутренние подотрезки дают вклад через векторное произведение, внешние — через угол сектора. Благодаря этому оптимизатор работает с аналитическим вычислителем, а не с дискретной аппроксимацией.
На этапе поиска оцениваются 23 стартовые точки, выбираются 4 лучшие, из них запускаются проецированные проходы Nelder-Mead, а затем делается еще одно более мелкое уточнение вокруг текущего победителя. Конечное значение ограничивается интервалом \([0,A_T]\), чтобы убрать микроскопические численные выбросы. Путь на C++ распределяет треугольники между потоками и использует компенсированное суммирование при редукции; путь на Java применяет параллельную редукцию. Итог округляется до двух знаков после запятой.
Допустимых треугольников ровно 57 222. Для одного треугольника вычисление площади пересечения имеет постоянную стоимость: есть только 3 ребра, у каждого не более 2 внутренних пересечений с окружностью, значит число подотрезков ограничено сверху константой. Бюджет оптимизации тоже фиксирован: 23 начальные оценки, до 4 запусков по 90 итераций и 1 финальное уточнение на 50 итераций. Поэтому суммарное время на практике линейно по числу треугольников.
Память равна \(O(1)\) на поток сверх текущего треугольника и нескольких частичных сумм. Главная численная опасность — потеря точности при сложении большого числа вещественных значений, поэтому в C++-реализации используется компенсированное суммирование Кэхэна.
المسألة 966 تمر على جميع المثلثات ذات الأضلاع الصحيحة التي تحقق \(1 \le a \le b \le c\) و\(a+b>c\) و\(a+b+c \le 200\). لكل مثلث \(T\) نأخذ دائرة مساحتها مساوية تمامًا لمساحة \(T\)، ويسمح بوضع مركز الدائرة في أي نقطة داخل المثلث. الكمية الخاصة بمثلث واحد هي
$$I(a,b,c)=\max_{x\in T}\operatorname{area}\bigl(T\cap B(x,r)\bigr),\qquad r=\sqrt{\frac{A_T}{\pi}},$$
حيث إن \(A_T\) مساحة المثلث و\(B(x,r)\) هو القرص المغلق نصف قطره \(r\) ومركزه \(x\). والمطلوب في النهاية هو
$$S=\sum_{\substack{1\le a\le b\le c\\ a+b>c\\ a+b+c\le 200}} I(a,b,c).$$
عدد الثلاثيات المقبولة يساوي 57,222 بالضبط، ولذلك فالصعوبة الحقيقية ليست في التعداد، بل في حل مسألة تعظيم مستمرة بدقة لكل مثلث على حدة.
المنهج يتكوّن من طبقتين. أولًا نحسب مساحة التقاطع بين المثلث والقرص حسابًا تحليليًا عندما يكون المركز ثابتًا. ثم نبحث عدديًا عن الموضع الذي يعطي أكبر قيمة لهذه الدالة المستمرة داخل المثلث المغلق.
تُرتَّب الأضلاع بحيث \(a \le b \le c\)، ثم يوضع الضلع الأطول على محور x:
$$A=(0,0),\qquad B=(c,0),\qquad C=(x_C,y_C).$$
ومن قانون جيب التمام نحصل على
$$x_C=\frac{b^2+c^2-a^2}{2c},\qquad y_C=\sqrt{b^2-x_C^2}.$$
بهذه الطريقة نحصل على تمثيل معياري للمثلث. ويمكن كتابة المساحة بصيغة الضرب الاتجاهي أو بصيغة هيرون:
$$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}.$$
وبما أن مساحة الدائرة يجب أن تساوي مساحة المثلث، فإن نصف القطر هو
$$r=\sqrt{\frac{A_T}{\pi}}.$$
بعد ذلك تصبح المسألة هندسية موضعية بحتة: نختار \(x\in T\) بحيث تكبر مساحة \(T\cap B(x,r)\) قدر الإمكان.
عند تثبيت مركز مرشح \(x\)، لا نحرك الدائرة بل نترجم المثلث بمقدار \(-x\)، فتغدو الدائرة هي القرص \(B(0,r)\). خذ ضلعًا موجَّهًا طرفاه بعد الترجمة هما \(p\) و\(q\). نقاط التقاطع الداخلية مع محيط الدائرة تحقق
$$\|p+t(q-p)\|^2=r^2,\qquad 0<t<1.$$
وهذه معادلة تربيعية، لذا لا يمكن أن يكون للضلع أكثر من نقطتي تقاطع داخليتين. وبعد قطع الضلع عند هاتين النقطتين يصبح كل جزء فرعي واقعًا بالكامل داخل القرص أو بالكامل خارجه.
إذا كان لدينا جزء فرعي طرفاه \(u\) و\(v\) ومنتصفه \(m=(u+v)/2\)، فإن مساهمته تساوي
$$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}$$
السطر الأول يمثل مساحة مثلث موجّه بالنسبة إلى الأصل، والثاني يمثل مساحة قطاع دائري موجّه. وبعد جمع المساهمات على الأضلاع الثلاثة الموجَّهة وأخذ القيمة المطلقة نحصل على مساحة التقاطع الدقيقة لذلك المركز:
$$I(a,b,c;x)=\left|\sum_{e\in\partial T} C_e\right|.$$
بعد إدراج جميع نقاط تقاطع المستقيم مع الدائرة، لا يمكن لأي جزء فرعي أن يعبر حد الدائرة مرة أخرى. ولأن القرص مجموعة محدبة، فإن الجزء الفرعي كله يكون داخل القرص أو خارجه، باستثناء احتمال وقوع الطرفين على الحد. لذلك يكفي اختبار المنتصف لتحديد أي صيغة مغلقة يجب استخدامها.
وهذه هي الفكرة الثابتة الأساسية في حاسب المساحة. فالتقاطع المعقد ظاهريًا بين المثلث والدائرة يتحول إلى قائمة صغيرة من أجزاء الأضلاع، وكل جزء يعطي مساهمة صريحة مباشرة. لذلك لا حاجة إلى التقطيع الشبكي أو التكامل العددي أو العينات الزاوية.
عند \((a,b,c)=(3,4,5)\) تكون الإحداثيات المعيارية
$$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).$$
ومن ثم تكون المساحة
$$A_T=\frac12\cdot 5\cdot 2.4=6,$$
ويصبح نصف قطر الدائرة متساوية المساحة
$$r=\sqrt{\frac{6}{\pi}}\approx 1.3819766.$$
إحدى نقاط البدء في البحث هي مركز الدائرة الداخلية، أي النقطة الموزونة بأطوال الأضلاع:
$$\frac{3A+4B+5C}{3+4+5}=(3,1).$$
وعند تشغيل حاسب المساحة الدقيق داخل المحسّن نحصل على قيمة التحقق
$$I(3,4,5)\approx 4.593049.$$
كما تتحقق التطبيقات أيضًا من القيمة \(I(3,4,6)\approx 3.552564\)، وهي نقطة فحص عددية إضافية مهمة.
الدالة \(x\mapsto I(a,b,c;x)\) متصلة، والمنطقة الممكنة \(T\) مدمجة، لذا فالقيمة العظمى موجودة حتمًا. التنفيذ يبحث عنها عدديًا باستخدام Nelder-Mead متعدد البدايات مع الإسقاط على المثلث.
مجموعة البدايات ذات طبيعة هندسية وليست عشوائية. فشبكة إحداثيات باريцентрية مقامها \(5\) تعطي 21 مرشحًا، ثم يضاف إليها مركز الثقل ومركز الدائرة الداخلية. تُقيَّم جميع هذه البذور، وتُختار أفضل أربع نقاط لتبدأ منها المرحلة الأولى من Nelder-Mead، ثم تُعاد موضعة أفضل نتيجة بخطوة أصغر للتنقيح النهائي. وكل نقطة تجريبية تُسقَط إلى أقرب نقطة في المثلث، لذلك يبقى الشرط \(x\in T\) محفوظًا تلقائيًا.
بعد حساب القيمة العظمى لمثلث واحد، لا يبقى سوى جمع القيم على جميع الثلاثيات المقبولة. الخاصية البنيوية المهمة هنا هي الاستقلال: كل مثلث يعالج منفصلًا، وكل تقييم لدالة الهدف كلفته \(O(1)\) بفضل الصيغة الدقيقة المبنية على الأضلاع.
تبدأ تطبيقات C++ وPython وJava بتعداد جميع الثلاثيات التي تحقق \(1\le a\le b\le c\) ولا متساواة المثلث وحدّ المحيط \(200\). ولكل ثلاثية تُرتَّب الأضلاع، وتُبنى الإحداثيات المعيارية على محور x، وتُحسب المساحة ونصف قطر الدائرة متساوية المساحة، وكذلك طول الضلع الأكبر المستخدم لتحديد مقياس خطوات البحث.
عند تثبيت مركز معين، يترجم التنفيذ المثلث بحيث يصبح القرص متمركزًا عند الأصل. ثم تُحل المعادلة التربيعية الخاصة بكل ضلع للحصول على معاملات تقاطع المستقيم مع الدائرة، ويُقسَّم الضلع إلى أجزاء فرعية. الأجزاء الداخلية تسهم بحد قائم على الضرب الاتجاهي، والأجزاء الخارجية تسهم بحد قائم على زاوية قطاع دائري. وبهذا يتعامل المحسّن مع حاسب هندسي تحليلي لا مع تقريب شبكي.
في مرحلة البحث تُقيَّم 23 نقطة ابتدائية، وتُختار أفضل 4 نقاط، ويُشغَّل Nelder-Mead مع الإسقاط من كل واحدة منها، ثم تُجرى مرحلة تنقيح أخيرة بخطوة أصغر حول أفضل نقطة عُثر عليها. وتُقيد القيمة النهائية داخل المجال \([0,A_T]\) لتفادي تجاوزات عددية طفيفة. مسار C++ يوزع المثلثات على عدة خيوط ويستخدم الجمع التعويضي عند الاختزال، أما مسار Java فيستخدم اختزالًا موازيًا. وفي النهاية يُقرَّب المجموع إلى منزلتين عشريتين.
عدد المثلثات المقبولة هو 57,222 بالضبط. وبالنسبة إلى مثلث واحد، فإن تقييم مساحة التقاطع زمنه ثابت: لدينا 3 أضلاع فقط، وكل ضلع ينتج في أقصى الأحوال نقطتي تقاطع داخليتين مع الدائرة، ومن ثم يبقى عدد الأجزاء الفرعية محدودًا بثابت. كما أن ميزانية البحث ثابتة أيضًا: 23 تقييمًا ابتدائيًا، وحتى 4 تشغيلات أولية من 90 تكرارًا، ثم تنقيح نهائي من 50 تكرارًا. لذلك يكون الزمن الكلي عمليًا خطيًا في عدد المثلثات.
استهلاك الذاكرة هو \(O(1)\) لكل عامل بالإضافة إلى المثلث الحالي وعدد صغير من المجاميع الجزئية. وأهم خطر عددي هو فقدان الدقة عند جمع عدد كبير من القيم العائمة، ولهذا يستخدم تنفيذ C++ جمع كاهان التعويضي في الاختزال النهائي.