A Heron envelope can be modeled as a rectangle of width \(2a\) and height \(h\), topped by an isosceles flap whose base is also \(2a\), whose equal side length is \(s\), and whose altitude is \(t\). Its outer perimeter is
$$P=2(a+h+s).$$
The task is to compute \(S(p)\), the sum of all such perimeters with \(P\le p\), subject to the geometric condition \(t<h\) and the integrality conditions encoded by the three reference implementations. Writing \(L=p/2\) is convenient, because every valid envelope then satisfies
$$a+h+s\le L.$$
The key observation is that every admissible envelope is governed by three right triangles sharing the same half-width \(a\). Once those right triangles are parameterized, the problem becomes a structured matching problem rather than a brute-force search over polygons.
The flap itself splits into two congruent right triangles, so its side length \(s\) must satisfy
$$a^2+t^2=s^2.$$
The rectangle has full width \(2a\), so its diagonal condition is
$$\left(2a\right)^2+h^2=d^2$$
for some integer \(d\).
The long diagonal running from a lower corner to the top vertex of the flap has horizontal offset \(a\) and vertical offset \(h+t\), so it must satisfy
$$a^2+(h+t)^2=q^2$$
for some integer \(q\).
Therefore a valid envelope is exactly a quadruple \((a,h,t,s)\) with
$$a^2+t^2=s^2,\qquad \left(2a\right)^2+h^2=d^2,\qquad a^2+(h+t)^2=q^2,\qquad t<h,\qquad a+h+s\le L.$$
Every primitive Pythagorean triple can be written as
$$x=m^2-n^2,\qquad y=2mn,\qquad z=m^2+n^2,$$
with \(m>n\), \(\gcd(m,n)=1\), and opposite parity. Multiplying by a positive scale \(k\) gives every non-primitive triple:
$$x=k(m^2-n^2),\qquad y=k(2mn),\qquad z=k(m^2+n^2).$$
For flap candidates, one leg is \(a\), the other is \(t\), and the hypotenuse is \(s\). Since either leg may play the role of \(a\), the implementations keep both leg orders from each generated triple.
For rectangle candidates, the full width must be \(2a\). So whenever a generated leg is even, that leg can be halved to obtain \(a\), while the other leg becomes \(h\). This is why the rectangle catalogue is built from Pythagorean triples with an even leg.
The perimeter bound gives safe search limits. Because \(a+h+s\le L\), we only need flap triples with \(s\le L\), and rectangle triples with \(2a\le 2L\) and \(h\le L\).
Define
$$T(a)=\left\{y\in\mathbb{Z}_{>0}:a^2+y^2\text{ is a perfect square}\right\}.$$
Then the flap condition says \(t\in T(a)\), and the long-diagonal condition says \(h+t\in T(a)\).
The rectangle condition is separate: \(h\) must belong to the set of heights for which \(\left(2a\right)^2+h^2\) is a square.
This immediately suggests the data organization used by the implementations: build all flap candidates and all rectangle candidates, then group both collections by the same value of \(a\). Each group can be processed independently.
Fix one half-width \(a\). For every rectangle height \(h\) in that group and every flap candidate \((t,s)\) in the same group, we test three conditions:
$$t<h,\qquad s\le L-a-h,\qquad h+t\in T(a).$$
The first inequality is the sensible-envelope condition. The second is just the perimeter bound rewritten from \(a+h+s\le L\). The third guarantees that the long diagonal is integral.
If all three tests pass, then the envelope is valid and contributes
$$2(a+h+s)$$
to \(S(p)\).
This is much cheaper than checking arbitrary polygons, because the search only combines already-valid right-triangle building blocks.
Within a fixed \(a\)-group, the flap candidates are sorted by \(t\). For fixed \(a\), the flap side length is
$$s=\sqrt{a^2+t^2},$$
so increasing \(t\) also increases \(s\). Therefore, once \(t\ge h\), no later flap can satisfy \(t<h\); and once \(s>L-a-h\), no later flap can satisfy the perimeter bound. Both facts allow early exits in the inner scan.
The rectangle heights are also sorted, so if \(L-a-h\le 0\), no larger height can work either. These monotonicity properties are exactly what make the grouped scan practical.
One concrete valid envelope is obtained from
$$a=60,\qquad h=119,\qquad t=25,\qquad s=65.$$
The flap is integral because
$$60^2+25^2=65^2.$$
The rectangle diagonal is integral because
$$120^2+119^2=169^2.$$
The long diagonal is also integral because
$$60^2+(119+25)^2=60^2+144^2=156^2.$$
Since \(25<119\), the flap is lower than the rectangle height as required. Its perimeter is
$$P=2(60+119+65)=488.$$
So this envelope contributes \(488\) to \(S(p)\) whenever \(p\ge 488\).
The C++, Python, and Java implementations all follow the same mathematical plan. They first set \(L=p/2\), generate all flap right triangles up to hypotenuse \(L\), and generate all rectangle candidates by taking Pythagorean triples whose even leg can serve as the full width \(2a\).
Next, they regroup both catalogues by the shared half-width \(a\). Inside each group, flap candidates are stored as altitude-side pairs \((t,s)\), and rectangle candidates are stored by their heights \(h\). A lookup structure containing all admissible values of \(t\) for that \(a\) lets the implementation test the long-diagonal condition \(h+t\in T(a)\) in constant expected time.
Each group is then scanned in sorted order. For every rectangle height, the implementation checks flap candidates until either \(t\ge h\) or \(s>L-a-h\). Every successful match adds \(2(a+h+s)\) to the running total. The C++ version additionally parallelizes these independent \(a\)-groups for large limits, while the Python and Java versions keep the same logic in a single thread.
Let \(T\) be the number of generated flap candidates and \(R\) the number of generated rectangle candidates after the Euclidean enumeration and scaling steps. Building those candidate lists is \(O(T+R)\) in output size, up to the arithmetic cost of the gcd filters and loop bounds in the triple generator.
Grouping and sorting cost
$$O(T\log T+R\log R)$$
overall. The matching phase is best described groupwise: if \(M\) is the total number of flap-rectangle pairs actually inspected before the early breaks trigger, then the scan costs \(O(M)\), and each long-diagonal test is \(O(1)\) on average thanks to the lookup structure.
Memory usage is linear in the stored candidates, plus the auxiliary membership structure used for the \(h+t\) test. In practice, the method is efficient because it never searches arbitrary envelopes directly; it only combines prevalidated right triangles with the same half-width.
Ein Heron-Umschlag kann als Rechteck der Breite \(2a\) und Höhe \(h\) modelliert werden, auf dessen Oberkante eine gleichschenklige Klappe mit derselben Basis \(2a\), den Schenkeln \(s\) und der Höhe \(t\) sitzt. Der Außenumfang ist
$$P=2(a+h+s).$$
Gesucht ist \(S(p)\), also die Summe aller solchen Umfänge mit \(P\le p\), unter der Zusatzbedingung \(t<h\) sowie den Ganzzahligkeitsbedingungen, die in den drei Referenzimplementierungen getestet werden. Mit \(L=p/2\) lässt sich die Umfangsbedingung bequem als
$$a+h+s\le L$$
schreiben.
Die zentrale Beobachtung ist: Jeder zulässige Umschlag wird durch drei rechtwinklige Dreiecke mit derselben Halbbasis \(a\) beschrieben. Sobald diese Dreiecke parametrisiert sind, bleibt kein geometrisches Rätsel mehr übrig, sondern nur noch ein geordnetes Matchingproblem.
Die Klappe zerfällt in zwei kongruente rechtwinklige Dreiecke. Daher muss für die Schenkellänge \(s\) gelten
$$a^2+t^2=s^2.$$
Das Rechteck hat die volle Breite \(2a\), also erfüllt seine Diagonale
$$\left(2a\right)^2+h^2=d^2$$
für ein ganzzahliges \(d\).
Die lange Diagonale von einer unteren Ecke zur Spitze der Klappe hat horizontalen Abstand \(a\) und vertikalen Abstand \(h+t\). Deshalb muss auch
$$a^2+(h+t)^2=q^2$$
für ein ganzzahliges \(q\) gelten.
Ein gültiger Umschlag ist also genau ein Tupel \((a,h,t,s)\) mit
$$a^2+t^2=s^2,\qquad \left(2a\right)^2+h^2=d^2,\qquad a^2+(h+t)^2=q^2,\qquad t<h,\qquad a+h+s\le L.$$
Jedes primitive pythagoreische Tripel hat die Form
$$x=m^2-n^2,\qquad y=2mn,\qquad z=m^2+n^2,$$
wobei \(m>n\), \(\gcd(m,n)=1\) und \(m,n\) unterschiedliche Parität haben. Durch Skalierung mit \(k\ge 1\) entstehen alle nichtprimitiven Tripel:
$$x=k(m^2-n^2),\qquad y=k(2mn),\qquad z=k(m^2+n^2).$$
Für Klappenkandidaten ist eine Kathete \(a\), die andere \(t\), und die Hypotenuse ist \(s\). Da beide Katheten die Rolle von \(a\) übernehmen können, werden in den Implementierungen beide Reihenfolgen der Katheten gespeichert.
Für Rechteckkandidaten muss die volle Breite \(2a\) eine gerade Kathete sein. Deshalb wird bei jedem erzeugten Tripel geprüft, ob eine Kathete gerade ist; halbiert man diese, erhält man \(a\), und die andere Kathete wird zu \(h\).
Aus \(a+h+s\le L\) folgen sichere Suchgrenzen: Für die Klappe genügt \(s\le L\), und für Rechtecke reichen Kandidaten mit \(2a\le 2L\) und \(h\le L\).
Definiere
$$T(a)=\left\{y\in\mathbb{Z}_{>0}:a^2+y^2\text{ ein Quadrat ist}\right\}.$$
Dann bedeutet die Klappenbedingung \(t\in T(a)\), und die Bedingung für die lange Diagonale lautet \(h+t\in T(a)\).
Die Rechteckbedingung ist davon getrennt: \(h\) muss eine Höhe sein, für die \(\left(2a\right)^2+h^2\) quadratisch ist.
Genau daraus ergibt sich die Datenorganisation der Implementierungen: Zuerst werden alle Klappen- und Rechteckkandidaten erzeugt, danach werden beide Sammlungen nach demselben Wert \(a\) gruppiert. Jede Gruppe kann unabhängig ausgewertet werden.
Fixiere ein \(a\). Für jede Rechteckhöhe \(h\) dieser Gruppe und jeden Klappenkandidaten \((t,s)\) derselben Gruppe werden drei Tests geprüft:
$$t<h,\qquad s\le L-a-h,\qquad h+t\in T(a).$$
Die erste Ungleichung ist die Forderung \(t<h\). Die zweite ist lediglich die Umfangsbedingung in umgestellter Form. Die dritte stellt sicher, dass auch die lange Diagonale ganzzahlig ist.
Erfüllt ein Paar alle drei Bedingungen, dann ist der Umschlag gültig und trägt
$$2(a+h+s)$$
zur Summe \(S(p)\) bei.
Innerhalb einer festen \(a\)-Gruppe werden die Klappenkandidaten nach \(t\) sortiert. Für festes \(a\) ist aber
$$s=\sqrt{a^2+t^2},$$
also wächst \(s\) streng mit \(t\). Sobald daher \(t\ge h\) gilt, kann kein späterer Kandidat noch \(t<h\) erfüllen. Und sobald \(s>L-a-h\) erreicht ist, scheitern auch alle späteren Kandidaten an der Umfangsgrenze.
Auch die Rechteckhöhen werden sortiert. Ist einmal \(L-a-h\le 0\), kann keine größere Höhe mehr funktionieren. Diese Monotonie ist der Grund, warum der gruppierte Suchlauf in der Praxis schnell ist.
Ein konkreter gültiger Umschlag entsteht mit
$$a=60,\qquad h=119,\qquad t=25,\qquad s=65.$$
Die Klappe ist ganzzahlig, denn
$$60^2+25^2=65^2.$$
Die Rechtecksdiagonale ist ganzzahlig, denn
$$120^2+119^2=169^2.$$
Und auch die lange Diagonale ist ganzzahlig, weil
$$60^2+(119+25)^2=60^2+144^2=156^2.$$
Außerdem gilt \(25<119\). Der Umfang beträgt damit
$$P=2(60+119+65)=488.$$
Dieser Umschlag trägt also \(488\) zu \(S(p)\) bei, sobald \(p\ge 488\) ist.
Die C++-, Python- und Java-Implementierungen folgen demselben Plan. Zunächst setzen sie \(L=p/2\), erzeugen alle Klappendreiecke mit Hypotenuse höchstens \(L\) und alle Rechteckkandidaten, bei denen eine gerade Kathete die volle Breite \(2a\) liefert.
Anschließend werden beide Kataloge nach der gemeinsamen Halbbreite \(a\) umgruppiert. Innerhalb einer Gruppe werden die Klappenkandidaten als Paare \((t,s)\) gespeichert, die Rechteckkandidaten durch ihre Höhen \(h\). Eine Nachschlagestruktur für alle zulässigen \(t\)-Werte dieser Gruppe ermöglicht den Test \(h+t\in T(a)\) in konstanter erwarteter Zeit.
Danach scannt die Implementierung jede Gruppe in sortierter Reihenfolge. Für jede Rechteckhöhe werden Klappenkandidaten nur so lange geprüft, bis entweder \(t\ge h\) oder \(s>L-a-h\) eintritt. Jeder Treffer addiert \(2(a+h+s)\). Die C++-Version parallelisiert diese voneinander unabhängigen \(a\)-Gruppen für große Grenzen zusätzlich; Python und Java verwenden dieselbe Logik seriell.
Seien \(T\) die Zahl der erzeugten Klappenkandidaten und \(R\) die Zahl der erzeugten Rechteckkandidaten nach der euklidischen Parametrisierung und Skalierung. Das Aufbauen dieser Listen kostet \(O(T+R)\) in Ausgabengröße, zuzüglich des arithmetischen Aufwands der gcd-Filter und Schleifengrenzen.
Gruppierung und Sortierung kosten insgesamt
$$O(T\log T+R\log R).$$
Die Matchingphase beschreibt man am saubersten über die tatsächlich besuchten Paare: Wenn \(M\) die Zahl der Rechteck-Klappen-Paare ist, die vor den frühen Abbrüchen wirklich inspiziert werden, dann kostet dieser Schritt \(O(M)\), und jeder Test auf die lange Diagonale läuft dank der Nachschlagestruktur im Mittel in \(O(1)\).
Der Speicherverbrauch ist linear in der Zahl der gespeicherten Kandidaten, plus der Hilfsstruktur für den Test von \(h+t\). Effizient wird das Verfahren dadurch, dass es niemals beliebige Vielecke ausprobiert, sondern nur bereits gültige rechtwinklige Dreiecke mit identischer Halbbreite kombiniert.
Bir Heron zarfı, genişliği \(2a\) ve yüksekliği \(h\) olan bir dikdörtgen ile, onun üstüne oturan tabanı yine \(2a\) olan ikizkenar bir kapaktan oluşur. Kapağın eş kenar uzunluğu \(s\), yüksekliği ise \(t\) olsun. Dış çevre
$$P=2(a+h+s)$$
şeklindedir. İstenen büyüklük, \(P\le p\) koşulunu sağlayan tüm uygun zarfların çevre toplamı \(S(p)\)'dir. Uygunluk için hem \(t<h\) şartı aranır hem de referans uygulamaların denetlediği bütün ilgili uzunlukların tam sayı olması gerekir. \(L=p/2\) yazarsak her geçerli zarf için
$$a+h+s\le L$$
olur.
Asıl fikir şudur: Geometrik nesnenin tamamı, aynı yarı tabanı \(a\) paylaşan üç ayrı dik üçgenle ifade edilir. Bu üçgenler doğru biçimde üretildiğinde problem, düzensiz çokgen aramak yerine önceden doğrulanmış adayları eşleştirme problemine dönüşür.
Kapak iki eş dik üçgene ayrılır. Bu yüzden kapağın eğik kenarı \(s\) için
$$a^2+t^2=s^2$$
olmalıdır.
Dikdörtgenin tam genişliği \(2a\) olduğundan, dikdörtgen köşegeni için
$$\left(2a\right)^2+h^2=d^2$$
biçiminde bir tam sayı \(d\) bulunmalıdır.
Alt köşeden kapağın tepe noktasına giden uzun köşegenin yatay farkı \(a\), düşey farkı \(h+t\) olduğundan ayrıca
$$a^2+(h+t)^2=q^2$$
eşitliğini sağlayan bir tam sayı \(q\) gerekir.
Dolayısıyla geçerli bir zarf tam olarak şu koşulları sağlar:
$$a^2+t^2=s^2,\qquad \left(2a\right)^2+h^2=d^2,\qquad a^2+(h+t)^2=q^2,\qquad t<h,\qquad a+h+s\le L.$$
Her ilkel Pisagor üçlüsü
$$x=m^2-n^2,\qquad y=2mn,\qquad z=m^2+n^2$$
şeklinde yazılır; burada \(m>n\), \(\gcd(m,n)=1\) ve \(m-n\) tektir. Pozitif bir \(k\) ile ölçekleyince bütün ilkel olmayan üçlüler de elde edilir:
$$x=k(m^2-n^2),\qquad y=k(2mn),\qquad z=k(m^2+n^2).$$
Kapak adaylarında bir dik kenar \(a\), diğeri \(t\), hipotenüs ise \(s\)'dir. İki dik kenarın rolleri değişebileceği için uygulamalar her üretilen üçlüden iki bacak sırasını da kaydeder.
Dikdörtgen adaylarında ise tam genişlik \(2a\) olmak zorundadır. Bu nedenle üretilen üçlüde herhangi bir bacak çiftse, o bacak ikiye bölünerek \(a\) elde edilir; öteki bacak da \(h\) olur.
Çevre sınırı güvenli arama sınırları verir: \(a+h+s\le L\) olduğundan kapak üçlülerinde \(s\le L\) yeterlidir; dikdörtgen adaylarında da \(2a\le 2L\) ve \(h\le L\) sınırı yeterlidir.
Şu kümeyi tanımlayalım:
$$T(a)=\left\{y\in\mathbb{Z}_{>0}:a^2+y^2\text{ bir tam karedir}\right\}.$$
O zaman kapak koşulu \(t\in T(a)\), uzun köşegen koşulu ise \(h+t\in T(a)\) haline gelir.
Dikdörtgen koşulu bundan ayrıdır: \(h\), \(\left(2a\right)^2+h^2\) ifadesini tam kare yapan yüksekliklerden biri olmalıdır.
Bu yüzden uygulamaların veri düzeni doğrudan ortaya çıkar: önce tüm kapak adayları ve tüm dikdörtgen adayları üretilir, sonra ikisi de aynı \(a\) değerine göre kovalanır. Her grup bağımsız biçimde işlenebilir.
Sabit bir \(a\) alalım. Bu gruptaki her dikdörtgen yüksekliği \(h\) ve aynı gruptaki her kapak adayı \((t,s)\) için üç test yapılır:
$$t<h,\qquad s\le L-a-h,\qquad h+t\in T(a).$$
İlk eşitsizlik sensibility koşuludur. İkinci eşitsizlik, çevre sınırının \(a+h+s\le L\) biçiminde yeniden yazılmasıdır. Üçüncü test ise uzun köşegenin tam sayı olmasını garanti eder.
Bu üç koşul sağlanırsa zarf geçerlidir ve toplama
$$2(a+h+s)$$
kadar katkı yapar.
Sabit bir \(a\) grubu içinde kapak adayları \(t\)'ye göre sıralanır. Fakat sabit \(a\) için
$$s=\sqrt{a^2+t^2}$$
olduğundan \(t\) arttıkça \(s\) de artar. Bu yüzden bir noktadan sonra \(t\ge h\) olursa sonraki adayların hiçbiri sensibility koşulunu sağlayamaz; benzer biçimde \(s>L-a-h\) olduktan sonra sonraki adayların hiçbiri çevre sınırını geçemez.
Dikdörtgen yükseklikleri de sıralıdır. Eğer \(L-a-h\le 0\) olursa daha büyük yüksekliklerin hiçbiri mümkün değildir. Kodun erken kırılmaları tam olarak bu monotonluklara dayanır.
Somut bir geçerli zarf şu değerlerle elde edilir:
$$a=60,\qquad h=119,\qquad t=25,\qquad s=65.$$
Kapağın kenarı tam sayıdır çünkü
$$60^2+25^2=65^2.$$
Dikdörtgenin köşegeni tam sayıdır çünkü
$$120^2+119^2=169^2.$$
Uzun köşegen de tam sayıdır çünkü
$$60^2+(119+25)^2=60^2+144^2=156^2.$$
Ayrıca \(25<119\) olduğu için kapak yüksekliği uygun biçimde daha küçüktür. Çevre
$$P=2(60+119+65)=488$$
olur. Dolayısıyla \(p\ge 488\) olduğunda bu zarf \(S(p)\)'ye \(488\) ekler.
C++, Python ve Java uygulamaları aynı matematiksel planı izler. Önce \(L=p/2\) alınır; sonra hipotenüsü \(L\)'yi geçmeyen bütün kapak dik üçgenleri ve çift bacağı tam genişlik \(2a\) olabilecek bütün dikdörtgen adayları üretilir.
Sonraki adımda her iki aday havuzu ortak yarı taban \(a\)'ya göre yeniden gruplanır. Bir grubun içinde kapak adayları \((t,s)\) çiftleri olarak, dikdörtgen adayları ise yükseklik \(h\) değerleri olarak tutulur. Aynı gruptaki bütün uygun \(t\) değerlerini içeren bir üyelik yapısı, \(h+t\in T(a)\) testinin sabit beklenen zamanda yapılmasını sağlar.
Daha sonra her grup sıralı biçimde taranır. Her dikdörtgen yüksekliği için kapak adayları ancak \(t<h\) ve \(s\le L-a-h\) olduğu sürece incelenir. Başarılı her eşleşme \(2(a+h+s)\) ekler. C++ sürümü büyük sınırlar için bu bağımsız \(a\)-gruplarını paralel de çalıştırır; Python ve Java aynı mantığı tek iş parçacığında sürdürür.
\(T\), üretilen kapak adaylarının; \(R\) ise üretilen dikdörtgen adaylarının sayısı olsun. Euclid parametrelemesi ve ölçekleme sonrası bu listeleri kurmanın maliyeti çıktı boyutu açısından \(O(T+R)\)'dir; buna gcd süzmesi ve döngü sınırlarının aritmetik maliyeti eklenir.
Gruplama ve sıralama toplamda
$$O(T\log T+R\log R)$$
zaman alır. Eşleştirme aşamasında en temiz gösterim şöyledir: Erken kırılmalar gerçekleşmeden önce gerçekten ziyaret edilen flap-dikdörtgen çiftlerinin toplam sayısı \(M\) ise, bu tarama \(O(M)\) sürer. Uzun köşegenin kontrolü ise üyelik yapısı sayesinde ortalama \(O(1)\)'dir.
Bellek kullanımı, saklanan aday sayısına göre lineerdir; buna \(h+t\) kontrolü için gereken yardımcı yapı eklenir. Yöntem pratikte hızlıdır, çünkü rastgele zarfları denemek yerine yalnızca aynı yarı tabanı paylaşan, önceden doğrulanmış dik üçgenleri birleştirir.
Un sobre de Herón puede modelarse como un rectángulo de ancho \(2a\) y altura \(h\), rematado por una solapa isósceles cuya base también mide \(2a\), cuyos lados iguales miden \(s\), y cuya altura es \(t\). Su perímetro exterior vale
$$P=2(a+h+s).$$
Se pide calcular \(S(p)\), la suma de todos esos perímetros con \(P\le p\), imponiendo además la condición geométrica \(t<h\) y las condiciones de integridad que verifican las tres implementaciones de referencia. Si escribimos \(L=p/2\), entonces todo sobre válido satisface
$$a+h+s\le L.$$
La observación decisiva es que todo sobre admisible queda determinado por tres triángulos rectángulos que comparten el mismo semiancho \(a\). Una vez parametrizados esos triángulos, el problema deja de ser una búsqueda geométrica abierta y pasa a ser un emparejamiento organizado de candidatos enteros.
La solapa se divide en dos triángulos rectángulos congruentes, así que su lado inclinado \(s\) debe cumplir
$$a^2+t^2=s^2.$$
El rectángulo tiene ancho completo \(2a\), por lo que su diagonal exige
$$\left(2a\right)^2+h^2=d^2$$
para algún entero \(d\).
La diagonal larga que va desde una esquina inferior hasta el vértice superior de la solapa tiene desplazamiento horizontal \(a\) y vertical \(h+t\), de modo que también debe cumplirse
$$a^2+(h+t)^2=q^2$$
para algún entero \(q\).
Así, un sobre válido es exactamente una cuádrupla \((a,h,t,s)\) con
$$a^2+t^2=s^2,\qquad \left(2a\right)^2+h^2=d^2,\qquad a^2+(h+t)^2=q^2,\qquad t<h,\qquad a+h+s\le L.$$
Toda terna pitagórica primitiva puede escribirse como
$$x=m^2-n^2,\qquad y=2mn,\qquad z=m^2+n^2,$$
con \(m>n\), \(\gcd(m,n)=1\) y paridad opuesta. Multiplicando por un factor \(k\ge 1\) obtenemos todas las ternas no primitivas:
$$x=k(m^2-n^2),\qquad y=k(2mn),\qquad z=k(m^2+n^2).$$
Para las solapas, una de las catetos actúa como \(a\), el otro como \(t\), y la hipotenusa es \(s\). Como cualquiera de los dos catetos puede desempeñar el papel de \(a\), las implementaciones guardan ambos órdenes posibles.
Para los rectángulos, el ancho completo debe ser \(2a\). Por eso, cuando una terna generada tiene un cateto par, ese cateto se puede dividir entre dos para obtener \(a\), y el otro cateto pasa a ser \(h\).
La cota del perímetro proporciona límites seguros: como \(a+h+s\le L\), basta generar solapas con \(s\le L\), y rectángulos con \(2a\le 2L\) y \(h\le L\).
Definimos
$$T(a)=\left\{y\in\mathbb{Z}_{>0}:a^2+y^2\text{ es un cuadrado perfecto}\right\}.$$
Entonces la condición de la solapa se convierte en \(t\in T(a)\), y la condición de la diagonal larga pasa a ser \(h+t\in T(a)\).
La condición del rectángulo es distinta: \(h\) debe pertenecer al conjunto de alturas para las que \(\left(2a\right)^2+h^2\) es un cuadrado.
De aquí sale de forma natural la organización de datos usada por la implementación: primero se generan todos los candidatos de solapa y rectángulo, y luego ambas colecciones se agrupan por el mismo valor \(a\). Cada grupo puede procesarse de manera independiente.
Fijemos un valor de \(a\). Para cada altura de rectángulo \(h\) en ese grupo y cada candidato de solapa \((t,s)\) del mismo grupo, se verifican tres condiciones:
$$t<h,\qquad s\le L-a-h,\qquad h+t\in T(a).$$
La primera desigualdad impone que la solapa sea más baja que el rectángulo. La segunda no es más que la cota de perímetro reescrita a partir de \(a+h+s\le L\). La tercera garantiza que la diagonal larga también sea entera.
Si las tres pruebas son correctas, el sobre es válido y aporta
$$2(a+h+s)$$
a la suma \(S(p)\).
Dentro de un grupo con \(a\) fijo, los candidatos de solapa se ordenan por \(t\). Pero con \(a\) fijo también se cumple
$$s=\sqrt{a^2+t^2},$$
de modo que \(s\) crece junto con \(t\). Por tanto, una vez que \(t\ge h\), ningún candidato posterior puede satisfacer \(t<h\); y una vez que \(s>L-a-h\), ningún candidato posterior puede respetar la cota del perímetro.
Las alturas del rectángulo también se ordenan. Si en algún momento \(L-a-h\le 0\), ninguna altura mayor puede funcionar. Esas monotonicidades explican por qué la exploración agrupada resulta eficaz.
Un sobre válido concreto se obtiene con
$$a=60,\qquad h=119,\qquad t=25,\qquad s=65.$$
La solapa es entera porque
$$60^2+25^2=65^2.$$
La diagonal del rectángulo es entera porque
$$120^2+119^2=169^2.$$
La diagonal larga también es entera porque
$$60^2+(119+25)^2=60^2+144^2=156^2.$$
Además, \(25<119\). El perímetro vale entonces
$$P=2(60+119+65)=488.$$
Así, este sobre contribuye con \(488\) a \(S(p)\) siempre que \(p\ge 488\).
Las implementaciones en C++, Python y Java siguen el mismo plan matemático. Primero fijan \(L=p/2\), generan todos los triángulos rectángulos de solapa con hipotenusa a lo sumo \(L\), y generan todos los candidatos de rectángulo en los que un cateto par puede actuar como ancho completo \(2a\).
Después reagrupan ambos catálogos por el semiancho compartido \(a\). Dentro de cada grupo, los candidatos de solapa se guardan como pares \((t,s)\), y los candidatos de rectángulo como alturas \(h\). Una estructura de pertenencia que contiene todos los valores admisibles de \(t\) para ese \(a\) permite comprobar la condición \(h+t\in T(a)\) en tiempo esperado constante.
A continuación, cada grupo se recorre en orden. Para cada altura de rectángulo, se examinan candidatos de solapa solo mientras se cumplan \(t<h\) y \(s\le L-a-h\). Cada coincidencia válida añade \(2(a+h+s)\) al total. La versión en C++ además paraleliza estos grupos independientes cuando el límite es grande; las versiones en Python y Java mantienen exactamente la misma lógica en un solo hilo.
Sean \(T\) el número de candidatos de solapa generados y \(R\) el número de candidatos de rectángulo generados tras la enumeración euclidiana y el escalado. Construir esas listas cuesta \(O(T+R)\) en tamaño de salida, aparte del coste aritmético de los filtros de gcd y de los límites de los bucles.
Agrupar y ordenar cuesta en total
$$O(T\log T+R\log R).$$
La fase de emparejamiento se describe mejor por grupos: si \(M\) es el número total de pares rectángulo-solapa realmente inspeccionados antes de que actúen las salidas tempranas, entonces ese barrido cuesta \(O(M)\), y cada comprobación de la diagonal larga es \(O(1)\) en promedio gracias a la estructura de pertenencia.
El consumo de memoria es lineal en el número de candidatos almacenados, más la estructura auxiliar usada para verificar \(h+t\). En la práctica, el método es eficiente porque nunca busca polígonos arbitrarios: solo combina triángulos rectángulos ya validados que comparten el mismo semiancho.
Heron 信封可以这样建模：下方是一个宽 \(2a\)、高 \(h\) 的矩形，上方接着一个底边同样为 \(2a\) 的等腰三角形翻盖，翻盖的腰长为 \(s\)，高为 \(t\)。它的外周长为
$$P=2(a+h+s).$$
题目要求计算 \(S(p)\)，也就是所有满足 \(P\le p\) 的这类信封周长之和，并且还要满足几何上的“翻盖高度小于矩形高度”条件 \(t<h\)，以及三份参考实现实际检查的整数长度条件。把
$$L=\frac{p}{2}$$
记作半周长上界后，每个合法信封都满足
$$a+h+s\le L.$$
核心思想是：整个图形并不需要直接按多边形去枚举，它本质上由三个共享同一个半宽 \(a\) 的直角三角形条件决定。只要先把这些直角三角形参数化，再按共享的 \(a\) 把候选项配对，问题就会从几何暴力搜索变成一个有结构的整数匹配问题。
翻盖是一个底边为 \(2a\) 的等腰三角形，把它从中线切开后会得到两个全等的直角三角形，因此翻盖腰长 \(s\) 必须满足
$$a^2+t^2=s^2.$$
矩形的完整宽度是 \(2a\)，所以矩形对角线整数条件应写成
$$\left(2a\right)^2+h^2=d^2$$
其中 \(d\) 是某个整数。
另外，从矩形下角连到翻盖顶点的那条长对角线，其水平位移是 \(a\)，竖直位移是 \(h+t\)，因此还必须满足
$$a^2+(h+t)^2=q^2$$
其中 \(q\) 也是整数。
于是，一个合法信封等价于满足下列条件的四元组 \((a,h,t,s)\)：
$$a^2+t^2=s^2,\qquad \left(2a\right)^2+h^2=d^2,\qquad a^2+(h+t)^2=q^2,\qquad t<h,\qquad a+h+s\le L.$$
任何原始勾股数都可以写成
$$x=m^2-n^2,\qquad y=2mn,\qquad z=m^2+n^2,$$
其中 \(m>n\)、\(\gcd(m,n)=1\)、而且 \(m,n\) 一奇一偶。再乘上正整数比例 \(k\)，就能得到所有非原始勾股三元组：
$$x=k(m^2-n^2),\qquad y=k(2mn),\qquad z=k(m^2+n^2).$$
对于翻盖候选，两个直角边分别扮演 \(a\) 和 \(t\)，斜边扮演 \(s\)。由于哪一条直角边是 \(a\) 并不固定，所以实现会把每个勾股三元组的两种直角边顺序都保留下来。
对于矩形候选，完整宽度必须是 \(2a\)，因此需要一条偶数直角边。只要生成出的某条直角边是偶数，就可以把它除以 \(2\) 得到 \(a\)，另一条直角边则作为矩形高度 \(h\)。
周长上界给出了安全的搜索范围。因为 \(a+h+s\le L\)，所以翻盖只需要考虑 \(s\le L\) 的勾股三元组；矩形只需要考虑满足 \(2a\le 2L\) 且 \(h\le L\) 的候选。
定义集合
$$T(a)=\left\{y\in\mathbb{Z}_{>0}:a^2+y^2\text{ 是完全平方数}\right\}.$$
那么翻盖条件就等价于 \(t\in T(a)\)，而长对角线条件则等价于 \(h+t\in T(a)\)。
矩形条件是另一类约束：\(h\) 必须来自那些让 \(\left(2a\right)^2+h^2\) 成为完全平方数的高度。
这正好解释了三份实现的组织方式。它们先分别生成“翻盖候选”和“矩形候选”，然后都按照同一个半宽 \(a\) 重新归桶。这样每个 \(a\)-组都可以独立处理，不同组之间互不影响。
固定某个半宽 \(a\)。对这个组里的每个矩形高度 \(h\)，以及同组里的每个翻盖候选 \((t,s)\)，需要检查三件事：
$$t<h,\qquad s\le L-a-h,\qquad h+t\in T(a).$$
第一条是题目要求的“翻盖不能高于矩形”。第二条只是把 \(a+h+s\le L\) 改写后得到的周长限制。第三条则保证从下角到翻盖顶点的长对角线也是整数。
如果这三项都成立，那么该信封就是合法的，并且会向总和 \(S(p)\) 贡献
$$2(a+h+s).$$
在固定 \(a\) 的组内，翻盖候选会按 \(t\) 从小到大排序。对固定 \(a\) 而言，翻盖腰长满足
$$s=\sqrt{a^2+t^2},$$
所以 \(t\) 越大，\(s\) 也越大。于是，一旦某个候选已经满足 \(t\ge h\)，后面的候选就不可能再满足 \(t<h\)；同样，一旦某个候选已经满足 \(s>L-a-h\)，后面的候选也都不可能再通过周长约束。
矩形高度同样会排序。如果某一步已经有 \(L-a-h\le 0\)，那么更大的高度也全部无效。代码里的提前跳出逻辑，正是利用了这些单调性。
下面给出一个完全符合实现判定条件的具体信封：
$$a=60,\qquad h=119,\qquad t=25,\qquad s=65.$$
先看翻盖，有
$$60^2+25^2=65^2,$$
所以翻盖两腰确实是整数。
再看矩形，对角线条件为
$$120^2+119^2=169^2,$$
因此矩形对角线也是整数。
最后看长对角线，因为
$$60^2+(119+25)^2=60^2+144^2=156^2,$$
所以从下角到翻盖顶点的长对角线同样是整数。
又因为 \(25<119\)，翻盖高度满足题目要求。它的周长为
$$P=2(60+119+65)=488.$$
因此只要 \(p\ge 488\)，这个信封就会向 \(S(p)\) 贡献 \(488\)。这个例子也清楚展示了实现中三个整数条件是如何同时工作的。
C++、Python 和 Java 三份实现采用的是同一套数学逻辑。第一步先设 \(L=p/2\)，然后枚举所有斜边不超过 \(L\) 的翻盖直角三角形，再枚举所有可以由偶数直角边提供完整宽度 \(2a\) 的矩形候选。
第二步把两类候选都按共享的半宽 \(a\) 分组。在每个组内部，翻盖候选保存为 \((t,s)\) 对，矩形候选只保留高度 \(h\)。同时还会建立一个针对该组的成员查询结构，用来快速判断某个值是否属于 \(T(a)\)，也就是判断 \(h+t\) 能否与同一个 \(a\) 组成新的勾股关系。
第三步是排序后的扫描。对每个矩形高度，程序只继续检查那些同时满足 \(t<h\) 和 \(s\le L-a-h\) 的翻盖候选；一旦某个条件不再可能成立，就可以立即停止当前扫描。每个成功匹配都会把 \(2(a+h+s)\) 累加进答案。C++ 版本还会在上界较大时把彼此独立的 \(a\)-组并行处理，而 Python 与 Java 版本则按同样的逻辑串行执行。
设通过欧几里得公式与缩放生成的翻盖候选总数为 \(T\)，矩形候选总数为 \(R\)。构造这两张候选表的成本，按输出规模计是 \(O(T+R)\)，外加 gcd 过滤与循环控制所需的算术开销。
后续的分组与排序总代价为
$$O(T\log T+R\log R).$$
匹配阶段最自然的写法是用实际访问的配对数来描述。设在所有提前停止条件生效之前，真正被检查过的“矩形候选-翻盖候选”配对总数为 \(M\)，那么这一阶段的扫描成本就是 \(O(M)\)。而 \(h+t\) 的整数对角线检查借助成员查询结构，平均只需 \(O(1)\) 时间。
空间复杂度对已保存的候选数是线性的，再加上用于成员测试的辅助结构。这个方法之所以高效，是因为它从头到尾都不直接枚举任意多边形，而是只组合那些已经通过勾股条件验证的构件。
Конверт Heron удобно описывать как прямоугольник ширины \(2a\) и высоты \(h\), над которым расположена равнобедренная створка с той же основанием \(2a\), боковой стороной \(s\) и высотой \(t\). Внешний периметр такой фигуры равен
$$P=2(a+h+s).$$
Нужно вычислить \(S(p)\), то есть сумму всех таких периметров при условии \(P\le p\), причем должны выполняться и геометрическое ограничение \(t<h\), и все целочисленные условия, которые проверяют три эталонные реализации. Если обозначить \(L=p/2\), то для любого допустимого конверта имеем
$$a+h+s\le L.$$
Главная идея состоит в том, что вся геометрия задачи сводится к трем прямоугольным треугольникам с общей полушириной \(a\). После параметризации этих треугольников уже не нужно перебирать произвольные многоугольники: остается только согласованно сочетать заранее построенные целочисленные блоки.
Створка распадается на два равных прямоугольных треугольника, поэтому ее боковая сторона \(s\) обязана удовлетворять равенству
$$a^2+t^2=s^2.$$
У прямоугольника полная ширина равна \(2a\), следовательно его диагональ должна удовлетворять
$$\left(2a\right)^2+h^2=d^2$$
для некоторого целого \(d\).
Длинная диагональ, идущая из нижнего угла к вершине створки, имеет горизонтальное смещение \(a\) и вертикальное смещение \(h+t\), поэтому требуется еще и
$$a^2+(h+t)^2=q^2$$
для некоторого целого \(q\).
Итак, допустимый конверт - это в точности набор \((a,h,t,s)\), для которого выполняется
$$a^2+t^2=s^2,\qquad \left(2a\right)^2+h^2=d^2,\qquad a^2+(h+t)^2=q^2,\qquad t<h,\qquad a+h+s\le L.$$
Любая примитивная пифагорова тройка имеет вид
$$x=m^2-n^2,\qquad y=2mn,\qquad z=m^2+n^2,$$
где \(m>n\), \(\gcd(m,n)=1\), а \(m\) и \(n\) разной четности. Умножение на положительный коэффициент \(k\) дает все непримитивные тройки:
$$x=k(m^2-n^2),\qquad y=k(2mn),\qquad z=k(m^2+n^2).$$
Для кандидатов на створку один катет играет роль \(a\), другой - роль \(t\), а гипотенуза становится \(s\). Поскольку любой из двух катетов может быть выбран как \(a\), реализации сохраняют оба порядка катетов.
Для кандидатов на прямоугольник полная ширина должна быть равна \(2a\). Поэтому, если в сгенерированной тройке один катет четный, его можно поделить пополам и получить \(a\), а второй катет станет высотой \(h\).
Ограничение на периметр задает безопасные границы перечисления. Из \(a+h+s\le L\) следует, что для створки достаточно рассматривать тройки с \(s\le L\), а для прямоугольника - случаи с \(2a\le 2L\) и \(h\le L\).
Введем множество
$$T(a)=\left\{y\in\mathbb{Z}_{>0}:a^2+y^2\text{ является полным квадратом}\right\}.$$
Тогда условие на створку превращается в \(t\in T(a)\), а условие на длинную диагональ - в \(h+t\in T(a)\).
Прямоугольное условие отделено от этого: \(h\) должен быть такой высотой, что \(\left(2a\right)^2+h^2\) является квадратом.
Отсюда естественным образом возникает организация данных, повторяющая реализацию: сначала строятся все кандидаты на створки и прямоугольники, а затем обе коллекции группируются по одному и тому же значению \(a\). Каждая группа обрабатывается независимо.
Зафиксируем \(a\). Для каждой высоты прямоугольника \(h\) в этой группе и каждого кандидата на створку \((t,s)\) в той же группе проверяются три условия:
$$t<h,\qquad s\le L-a-h,\qquad h+t\in T(a).$$
Первое неравенство выражает требование \(t<h\). Второе - это просто ограничение на периметр, переписанное из \(a+h+s\le L\). Третье гарантирует целочисленность длинной диагонали.
Если все три проверки пройдены, то конверт допустим и дает вклад
$$2(a+h+s)$$
в сумму \(S(p)\).
Внутри фиксированной группы по \(a\) кандидаты на створку сортируются по \(t\). Но при фиксированном \(a\) длина боковой стороны равна
$$s=\sqrt{a^2+t^2},$$
поэтому с ростом \(t\) строго растет и \(s\). Значит, как только достигнуто \(t\ge h\), ни один более поздний кандидат уже не сможет выполнить \(t<h\); а как только \(s>L-a-h\), все следующие кандидаты также нарушат ограничение на периметр.
Высоты прямоугольников тоже сортируются. Если уже получилось \(L-a-h\le 0\), то никакая большая высота не подойдет. Именно на этих монотонностях основаны ранние выходы из внутренних циклов.
Конкретный допустимый конверт получается при
$$a=60,\qquad h=119,\qquad t=25,\qquad s=65.$$
Створка корректна, потому что
$$60^2+25^2=65^2.$$
Диагональ прямоугольника целая, так как
$$120^2+119^2=169^2.$$
Длинная диагональ тоже целая, поскольку
$$60^2+(119+25)^2=60^2+144^2=156^2.$$
Кроме того, \(25<119\). Следовательно, периметр равен
$$P=2(60+119+65)=488.$$
Значит, этот конверт добавляет \(488\) к \(S(p)\) для любого \(p\ge 488\).
Реализации на C++, Python и Java следуют одному и тому же плану. Сначала они вычисляют \(L=p/2\), затем генерируют все прямоугольные треугольники для створки с гипотенузой не больше \(L\), а также все кандидаты на прямоугольник, у которых четный катет может быть полной шириной \(2a\).
После этого обе коллекции перегруппировываются по общей полуширине \(a\). Внутри группы кандидаты на створку хранятся как пары \((t,s)\), а кандидаты на прямоугольник - как высоты \(h\). Дополнительная структура принадлежности для всех допустимых значений \(t\) в данной группе позволяет проверять условие \(h+t\in T(a)\) за константное ожидаемое время.
Затем каждая группа просматривается в отсортированном порядке. Для каждой высоты прямоугольника код рассматривает кандидаты на створку лишь до тех пор, пока одновременно возможны условия \(t<h\) и \(s\le L-a-h\). Каждый успешный матч добавляет \(2(a+h+s)\) к ответу. В C++-версии независимые группы по \(a\) дополнительно распараллеливаются при больших границах; в Python и Java используется та же логика без распараллеливания.
Пусть \(T\) - число сгенерированных кандидатов на створку, а \(R\) - число сгенерированных кандидатов на прямоугольник после евклидовой параметризации и масштабирования. Построение этих списков занимает \(O(T+R)\) по размеру выхода, не считая арифметической цены фильтров по gcd и границ циклов.
Группировка и сортировка требуют в сумме
$$O(T\log T+R\log R).$$
Фазу сопоставления удобно описывать через реально посещенные пары. Если \(M\) - общее число пар «прямоугольник-створка», которые были действительно проверены до срабатывания ранних остановок, то этот этап стоит \(O(M)\). Проверка длинной диагонали благодаря структуре принадлежности работает в среднем за \(O(1)\).
Память расходуется линейно по числу сохраненных кандидатов, плюс вспомогательная структура для теста \(h+t\). Метод эффективен потому, что он никогда не перебирает произвольные многоугольники напрямую, а только комбинирует уже валидные прямоугольные треугольники с одной и той же полушириной.
يمكن تمثيل غلاف Heron على أنه مستطيل عرضه \(2a\) وارتفاعه \(h\)، تعلوه رفرفة متساوية الساقين قاعدتها أيضًا \(2a\)، وطول كل ضلع مائل فيها هو \(s\)، وارتفاعها هو \(t\). محيط الشكل الخارجي يساوي
$$P=2(a+h+s).$$
المطلوب هو حساب \(S(p)\)، أي مجموع جميع هذه المحيطات عندما يكون \(P\le p\)، مع الشرط الهندسي \(t<h\) ومع جميع شروط التكامل التي تختبرها التطبيقات المرجعية الثلاثة. وإذا كتبنا
$$L=\frac{p}{2}$$
فإن كل غلاف صالح يحقق
$$a+h+s\le L.$$
الفكرة الأساسية هي أن الشكل كله لا يحتاج إلى فحصه مباشرة كمتعدد أضلاع عام، بل يمكن وصفه بالكامل عبر ثلاثة مثلثات قائمة تشترك في نصف العرض نفسه \(a\). وبعد توليد هذه المثلثات بصورة منهجية تتحول المسألة من بحث هندسي خام إلى عملية مطابقة منظمة بين مرشحين صحيحين.
الرفرفة تنقسم إلى مثلثين قائمين متطابقين، ولذلك يجب أن يحقق الضلع المائل \(s\) العلاقة
$$a^2+t^2=s^2.$$
أما المستطيل فعرضه الكامل هو \(2a\)، لذا فإن قطْره يجب أن يحقق
$$\left(2a\right)^2+h^2=d^2$$
لعدد صحيح ما \(d\).
والقطر الطويل الممتد من زاوية سفلية إلى رأس الرفرفة له إزاحة أفقية مقدارها \(a\) وإزاحة رأسية مقدارها \(h+t\)، ومن ثم يجب أيضًا أن يحقق
$$a^2+(h+t)^2=q^2$$
لعدد صحيح ما \(q\).
إذن الغلاف الصحيح هو بالضبط رباعية \((a,h,t,s)\) تحقق
$$a^2+t^2=s^2,\qquad \left(2a\right)^2+h^2=d^2,\qquad a^2+(h+t)^2=q^2,\qquad t<h,\qquad a+h+s\le L.$$
كل ثلاثية فيثاغورس أولية يمكن كتابتها على الصورة
$$x=m^2-n^2,\qquad y=2mn,\qquad z=m^2+n^2,$$
حيث \(m>n\)، و\(\gcd(m,n)=1\)، ويكون أحدهما زوجيًا والآخر فرديًا. ثم إن الضرب في معامل موجب \(k\) يولد جميع الثلاثيات غير الأولية:
$$x=k(m^2-n^2),\qquad y=k(2mn),\qquad z=k(m^2+n^2).$$
بالنسبة إلى مرشحي الرفرفة، يكون أحد الضلعين القائمين هو \(a\) والآخر هو \(t\)، والوتر هو \(s\). ولأن أيًّا من الضلعين القائمين قد يلعب دور \(a\)، فإن التطبيقات تحتفظ بالترتيبين معًا.
أما بالنسبة إلى مرشحي المستطيل، فلا بد أن يكون العرض الكامل هو \(2a\). لذلك إذا كان أحد الضلعين القائمين في ثلاثية مولدة عددًا زوجيًا، فيمكن قسمته على \(2\) للحصول على \(a\)، بينما يصبح الضلع الآخر هو الارتفاع \(h\).
يعطي حد المحيط حدودًا آمنة للتوليد. فمن \(a+h+s\le L\) نستنتج أن توليد الرفارف يكفي أن يقتصر على \(s\le L\)، وأن توليد المستطيلات يكفي أن يغطي الحالات التي فيها \(2a\le 2L\) و\(h\le L\).
نعرّف المجموعة
$$T(a)=\left\{y\in\mathbb{Z}_{>0}:\exists n\in\mathbb{Z}_{>0},\ a^2+y^2=n^2\right\}.$$
وعندئذ يصبح شرط الرفرفة هو \(t\in T(a)\)، بينما يصبح شرط القطر الطويل هو \(h+t\in T(a)\).
أما شرط المستطيل فهو منفصل: يجب أن يكون \(h\) من الارتفاعات التي تجعل \(\left(2a\right)^2+h^2\) مربعًا كاملاً.
ومن هنا تنشأ مباشرة طريقة تنظيم البيانات في التنفيذ. إذ تُولَّد أولاً جميع مرشحات الرفرفة وجميع مرشحات المستطيل، ثم تُجمَّع القائمتان بحسب القيمة نفسها \(a\). ويمكن معالجة كل مجموعة على حدة دون الاعتماد على المجموعات الأخرى.
لنثبت قيمة \(a\). ولكل ارتفاع مستطيل \(h\) في هذه المجموعة، ولكل مرشح رفرفة \((t,s)\) في المجموعة نفسها، تُفحَص الشروط الثلاثة التالية:
$$t<h,\qquad s\le L-a-h,\qquad h+t\in T(a).$$
الشرط الأول هو الشرط الهندسي \(t<h\). والشرط الثاني ليس إلا إعادة كتابة لقيد المحيط \(a+h+s\le L\). أما الشرط الثالث فيضمن أن القطر الطويل عدد صحيح أيضًا.
إذا تحققت الشروط كلها، كان الغلاف صالحًا وأضاف المقدار
$$2(a+h+s)$$
إلى المجموع \(S(p)\).
داخل المجموعة ذات \(a\) الثابتة، تُرتَّب مرشحات الرفرفة بحسب \(t\). لكن عند ثبوت \(a\) يكون
$$s=\sqrt{a^2+t^2},$$
ومن ثم فإن زيادة \(t\) تعني زيادة \(s\) أيضًا. لذلك، ما إن يصبح \(t\ge h\) حتى يستحيل على أي مرشح لاحق أن يحقق \(t<h\). وبالمثل، ما إن يصبح \(s>L-a-h\) حتى يستحيل على أي مرشح لاحق أن يمر من قيد المحيط.
كما تُرتَّب ارتفاعات المستطيل أيضًا. فإذا وصلنا إلى حالة \(L-a-h\le 0\)، فلن تنجح أي قيمة أكبر لـ \(h\). وهذه الرتابات هي التي تسمح بعمليات التوقف المبكر في المسح الداخلي.
يمكن بناء غلاف صحيح محدد من القيم
$$a=60,\qquad h=119,\qquad t=25,\qquad s=65.$$
فالرفرفة صحيحة لأن
$$60^2+25^2=65^2.$$
وقطر المستطيل صحيح لأن
$$120^2+119^2=169^2.$$
والقطر الطويل صحيح أيضًا لأن
$$60^2+(119+25)^2=60^2+144^2=156^2.$$
وفوق ذلك فإن \(25<119\)، أي إن شرط الرفرفة المعقول متحقق. لذلك يكون المحيط
$$P=2(60+119+65)=488.$$
وهذا يعني أن هذا الغلاف يضيف \(488\) إلى \(S(p)\) كلما كان \(p\ge 488\).
تسير تطبيقات C++ وPython وJava على الخطة الرياضية نفسها. أولاً تضبط \(L=p/2\)، ثم تولد جميع مثلثات الرفرفة القائمة التي لا يتجاوز وترها \(L\)، وبعد ذلك تولد جميع مرشحي المستطيل الذين يمكن أن يمثل فيهم ضلع قائم زوجي العرض الكامل \(2a\).
بعد ذلك يُعاد تنظيم القائمتين بحسب نصف العرض المشترك \(a\). داخل كل مجموعة، تُخزَّن مرشحات الرفرفة على صورة أزواج \((t,s)\)، بينما تُخزَّن مرشحات المستطيل على هيئة قيم الارتفاع \(h\). كما تُبنى بنية عضوية تحتوي على جميع قيم \(t\) المسموح بها لتلك المجموعة، بحيث يمكن اختبار الشرط \(h+t\in T(a)\) في زمن ثابت متوقع.
ثم تُمسَح كل مجموعة بترتيب تصاعدي. ولكل ارتفاع مستطيل، لا تستمر الشيفرة في فحص مرشحي الرفرفة إلا ما دام الشرطان \(t<h\) و\(s\le L-a-h\) ما زالا ممكنين. وكل تطابق ناجح يضيف \(2(a+h+s)\) إلى الإجابة. وتقوم نسخة C++، عند الحدود الكبيرة، بموازاة معالجة المجموعات المستقلة بحسب \(a\)، بينما تنفذ نسختا Python وJava المنطق نفسه بصورة تسلسلية.
ليكن \(T\) عدد مرشحي الرفرفة المولدين، و\(R\) عدد مرشحي المستطيل المولدين بعد استخدام صيغة إقليدس وعملية التوسيع. إن بناء هاتين القائمتين يكلف \(O(T+R)\) بحسب حجم المخرجات، بالإضافة إلى الكلفة الحسابية لمرشحات القاسم المشترك وحدود الحلقات.
أما التجميع والترتيب فيكلفان معًا
$$O(T\log T+R\log R).$$
ويُوصَف طور المطابقة بصورة أوضح عبر عدد الأزواج التي جرى فحصها فعلاً. فإذا كان \(M\) هو مجموع أزواج «مرشح مستطيل - مرشح رفرفة» التي زارتها الخوارزمية قبل أن توقفها شروط الإيقاف المبكر، فإن كلفة هذا الطور هي \(O(M)\). واختبار القطر الطويل يتم بمتوسط \(O(1)\) بفضل بنية العضوية.
استهلاك الذاكرة خطي في عدد المرشحين المخزنين، مع إضافة البنية المساعدة الخاصة باختبار \(h+t\). والسبب في فعالية الطريقة أنها لا تبحث أبدًا في جميع الأشكال الممكنة مباشرة، بل تجمع فقط بين مثلثات قائمة سبق التحقق منها وتشترك في نصف العرض نفسه.