Start with an equilateral triangle of side length \(n\), subdivided in the cross-hatched way described in the problem, and count every triangle whose three sides lie on drawn segments. For the Project Euler instance, \(n=36\).
The important point is that the implementations do not classify triangles by shape or size. Instead, they turn the whole picture into a finite arrangement of supporting lines and then count which triples of those lines really bound a triangle inside the outer hull.
The derivation is geometric rather than recursive. Once the cross-hatching is written as explicit families of lines, the problem becomes: among all triples of generated lines, how many have three pairwise intersections that are inside the big triangle and are not collapsed into a single point?
Set
$$h=\frac{\sqrt{3}}{2},\qquad A=(0,0),\qquad B=(n,0),\qquad C=\left(\frac{n}{2},nh\right).$$
This places the outer figure as a standard equilateral triangle. A point \(P\) lies inside or on the boundary precisely when it is on the left side of each directed edge \(AB\), \(BC\), and \(CA\). Using the oriented-area determinant
$$\det(P,Q,R)=(Q_x-P_x)(R_y-P_y)-(Q_y-P_y)(R_x-P_x),$$
the inside test is
$$\det(A,B,P)\ge 0,\qquad \det(B,C,P)\ge 0,\qquad \det(C,A,P)\ge 0.$$
Equivalently, in this coordinate system the hull is described by
$$y\ge 0,\qquad y\le \sqrt{3}\,x,\qquad y\le \sqrt{3}\,(n-x).$$
The code reveals that every drawn segment belongs to one of only six directions: horizontal, vertical, \(\pm 60^\circ\), and \(\pm 30^\circ\). After extending each drawn segment to its full supporting line, the families become
$$\begin{aligned} y &= kh, && 0\le k\le n-1,\\ x-\sqrt{3}\,y &= s, && -(n-1)\le s\le n-1,\\ x-\frac{y}{\sqrt{3}} &= k, && 0\le k\le n-1,\\ x+\frac{y}{\sqrt{3}} &= k+1, && 0\le k\le n-1,\\ x+\sqrt{3}\,y &= t, && 1\le t\le 2n-1,\\ x &= \frac{u}{2}, && 1\le u\le 2n-1. \end{aligned}$$
The family sizes are
$$n,\quad 2n-1,\quad n,\quad n,\quad 2n-1,\quad 2n-1,$$
so the total number of supporting lines is
$$M=n+(2n-1)+n+n+(2n-1)+(2n-1)=9n-3.$$
For \(n=36\), this is only \(M=321\) lines. That is the key reduction: the original picture looks complicated, but the entire counting problem is compressed into a modest finite line arrangement.
Each line is stored in coefficient form
$$ax+by=c,$$
where a line through \(P=(p_x,p_y)\) and \(Q=(q_x,q_y)\) uses
$$a=p_y-q_y,\qquad b=q_x-p_x,\qquad c=q_xp_y-p_xq_y.$$
For two lines \((a_1,b_1,c_1)\) and \((a_2,b_2,c_2)\), let
$$\Delta=a_1b_2-a_2b_1.$$
If \(\Delta=0\), the lines are parallel and cannot give a triangle vertex. Otherwise their unique intersection is
$$x=\frac{c_1b_2-c_2b_1}{\Delta},\qquad y=\frac{a_1c_2-a_2c_1}{\Delta}.$$
Any intersection outside the outer hull is discarded immediately. After this preprocessing, every unordered pair of lines is either marked invalid or assigned one concrete vertex inside the big triangle.
Take three generated lines \(\ell_1,\ell_2,\ell_3\). There are only three possibilities:
If some pair is parallel, at least one vertex is missing, so there is no triangle.
If all three pairwise intersections exist but two of them coincide, then the three lines are concurrent and the boundary degenerates at one point instead of forming three corners.
If the three pairwise intersections all exist and are three distinct points, then those points are the vertices of one and only one triangle whose sides lie on \(\ell_1,\ell_2,\ell_3\).
The converse is just as important: every triangle in the cross-hatched figure has three sides on three supporting lines from the list above, and those supporting lines are unique. So counting valid triples of lines counts every triangle exactly once.
When \(n=1\), the six families contribute exactly six lines:
$$y=0,\quad x-\sqrt{3}\,y=0,\quad x-\frac{y}{\sqrt{3}}=0,\quad x+\frac{y}{\sqrt{3}}=1,\quad x+\sqrt{3}\,y=1,\quad x=\frac{1}{2}.$$
Choose the three lines
$$y=0,\qquad x=\frac{1}{2},\qquad x+\sqrt{3}\,y=1.$$
Their pairwise intersections are
$$\left(\frac{1}{2},0\right),\qquad (1,0),\qquad \left(\frac{1}{2},\frac{1}{2\sqrt{3}}\right),$$
which are three distinct points inside the hull, so they contribute one triangle.
By contrast, the triple
$$y=0,\qquad x-\frac{y}{\sqrt{3}}=0,\qquad x-\sqrt{3}\,y=0$$
has all three pairwise intersections at \(A=(0,0)\), so it is rejected as degenerate. Running this criterion over all \(\binom{6}{3}=20\) triples leaves 16 triangles, matching the first checkpoint used by the implementations.
The C++, Python, and Java implementations start from a unit equilateral triangle with vertices \((0,0)\), \((1,0)\), and \((1/2,\sqrt{3}/2)\). Midpoints of the unit sides determine the \(\pm 30^\circ\) and vertical auxiliary families, and integer or half-integer translations generate every line needed for size \(n\).
This is why the line list is so regular: the same six prototype directions are simply shifted across the figure until all supporting lines of the cross-hatching have been emitted.
For each pair of lines, the implementation solves one \(2\times 2\) linear system. Parallel pairs are rejected by the determinant test. Nonparallel pairs are then filtered by the three oriented-area inequalities of the outer triangle, so only vertices that actually lie in the figure survive.
The result is a lookup table indexed by line pairs. Later stages never recompute an intersection; they only query whether a pair has a valid vertex and, if so, what that vertex is.
The final sweep considers every \(i<j<k\). A triple contributes exactly when the three stored pairwise intersections \((i,j)\), \((i,k)\), and \((j,k)\) are all valid and no two of those points are numerically equal.
A small floating-point tolerance is used in the equality test because all coordinates are built from rational numbers and \(\sqrt{3}\), so exact binary arithmetic is not available. The implementations also verify the geometric model on the small cases \(n=1\to 16\) and \(n=2\to 104\) before counting the full case.
Let \(M=9n-3\) be the number of generated lines. Pair preprocessing needs \(O(M^2)\) intersections, and the main triangle count checks all \(\binom{M}{3}\) triples, so the overall time is
$$O(M^3)=O(n^3).$$
The pair table uses
$$O(M^2)=O(n^2)$$
memory.
For the actual input \(n=36\), we have \(M=321\), hence only \(\binom{321}{2}=51360\) line pairs and \(\binom{321}{3}=5461280\) line triples. Those numbers are small enough that exhaustive geometric enumeration is entirely practical.
Man betrachtet ein gleichseitiges Dreieck der Seitenlänge \(n\), das genau in der im Problem beschriebenen kreuzschraffierten Weise unterteilt ist, und zählt alle Dreiecke, deren drei Seiten auf eingezeichneten Segmenten liegen. Im eigentlichen Project-Euler-Fall ist \(n=36\).
Die Implementierungen klassifizieren die Dreiecke nicht nach Typen. Stattdessen verwandeln sie die ganze Zeichnung in eine endliche Geradenanordnung und zählen dann, welche Dreiermengen dieser Geraden innerhalb der äußeren Hülle tatsächlich ein Dreieck begrenzen.
Die Herleitung ist rein geometrisch. Sobald die Schraffur als explizite Geradenfamilien formuliert ist, lautet das Problem: Für wie viele erzeugte Geradentripel existieren drei paarweise Schnittpunkte, die innerhalb des großen Dreiecks liegen und nicht zu einem einzigen Punkt zusammenfallen?
Setze
$$h=\frac{\sqrt{3}}{2},\qquad A=(0,0),\qquad B=(n,0),\qquad C=\left(\frac{n}{2},nh\right).$$
Damit liegt die äußere Figur als Standardmodell eines gleichseitigen Dreiecks vor. Ein Punkt \(P\) liegt genau dann im Inneren oder auf dem Rand, wenn er links von den gerichteten Kanten \(AB\), \(BC\) und \(CA\) liegt. Mit der orientierten Flächendeterminante
$$\det(P,Q,R)=(Q_x-P_x)(R_y-P_y)-(Q_y-P_y)(R_x-P_x)$$
lautet der Innentest
$$\det(A,B,P)\ge 0,\qquad \det(B,C,P)\ge 0,\qquad \det(C,A,P)\ge 0.$$
In diesen Koordinaten ist das äquivalent zu
$$y\ge 0,\qquad y\le \sqrt{3}\,x,\qquad y\le \sqrt{3}\,(n-x).$$
Der Code zeigt, dass jedes eingezeichnete Segment zu genau einer von sechs Richtungen gehört: horizontal, vertikal, \(\pm 60^\circ\) und \(\pm 30^\circ\). Verlängert man jedes Segment zu seiner Trägergeraden, erhält man die Familien
$$\begin{aligned} y &= kh, && 0\le k\le n-1,\\ x-\sqrt{3}\,y &= s, && -(n-1)\le s\le n-1,\\ x-\frac{y}{\sqrt{3}} &= k, && 0\le k\le n-1,\\ x+\frac{y}{\sqrt{3}} &= k+1, && 0\le k\le n-1,\\ x+\sqrt{3}\,y &= t, && 1\le t\le 2n-1,\\ x &= \frac{u}{2}, && 1\le u\le 2n-1. \end{aligned}$$
Die Größen dieser Familien sind
$$n,\quad 2n-1,\quad n,\quad n,\quad 2n-1,\quad 2n-1,$$
also insgesamt
$$M=n+(2n-1)+n+n+(2n-1)+(2n-1)=9n-3$$
Trägergeraden. Für \(n=36\) sind das nur \(M=321\) Geraden. Genau hier liegt die eigentliche Reduktion: Die Zeichnung wirkt unübersichtlich, aber das Zählproblem wird auf eine überschaubare endliche Geradenanordnung komprimiert.
Jede Gerade wird in Koeffizientenform
$$ax+by=c$$
gespeichert. Für eine Gerade durch \(P=(p_x,p_y)\) und \(Q=(q_x,q_y)\) verwendet die Implementierung
$$a=p_y-q_y,\qquad b=q_x-p_x,\qquad c=q_xp_y-p_xq_y.$$
Für zwei Geraden \((a_1,b_1,c_1)\) und \((a_2,b_2,c_2)\) sei
$$\Delta=a_1b_2-a_2b_1.$$
Falls \(\Delta=0\), sind die Geraden parallel. Sonst ist ihr eindeutiger Schnittpunkt
$$x=\frac{c_1b_2-c_2b_1}{\Delta},\qquad y=\frac{a_1c_2-a_2c_1}{\Delta}.$$
Liegt dieser Punkt außerhalb der äußeren Hülle, wird er sofort verworfen. Danach ist jedes ungeordnete Geradenpaar entweder ungültig oder liefert genau einen konkreten Eckpunkt im großen Dreieck.
Betrachte drei erzeugte Geraden \(\ell_1,\ell_2,\ell_3\). Es gibt nur drei Fälle:
Sind zwei davon parallel, fehlt mindestens ein Eckpunkt, also entsteht kein Dreieck.
Existieren zwar alle drei paarweisen Schnittpunkte, fallen aber zwei zusammen, dann sind die drei Geraden konkurrent, und die vermeintliche Begrenzung degeneriert in einem Punkt.
Existieren alle drei Schnittpunkte und sind sie paarweise verschieden, dann sind diese drei Punkte genau die Ecken eines eindeutig bestimmten Dreiecks, dessen Seiten auf \(\ell_1,\ell_2,\ell_3\) liegen.
Umgekehrt besitzt jedes Dreieck der Schraffur drei Seiten auf genau drei Trägergeraden aus der obigen Liste. Deshalb zählt das Verfahren jedes Dreieck genau einmal.
Für \(n=1\) tragen die sechs Familien genau sechs Geraden bei:
$$y=0,\quad x-\sqrt{3}\,y=0,\quad x-\frac{y}{\sqrt{3}}=0,\quad x+\frac{y}{\sqrt{3}}=1,\quad x+\sqrt{3}\,y=1,\quad x=\frac{1}{2}.$$
Wählt man
$$y=0,\qquad x=\frac{1}{2},\qquad x+\sqrt{3}\,y=1,$$
so sind die paarweisen Schnittpunkte
$$\left(\frac{1}{2},0\right),\qquad (1,0),\qquad \left(\frac{1}{2},\frac{1}{2\sqrt{3}}\right),$$
also drei verschiedene Punkte innerhalb der Hülle. Dieses Tripel liefert daher ein Dreieck.
Dagegen ist
$$y=0,\qquad x-\frac{y}{\sqrt{3}}=0,\qquad x-\sqrt{3}\,y=0$$
degeneriert, weil alle drei paarweisen Schnitte in \(A=(0,0)\) liegen. Von den insgesamt \(\binom{6}{3}=20\) Geradentripeln bleiben dadurch genau 16 gültige Dreiecke übrig, genau wie in der ersten Kontrollrechnung der Implementierungen.
Die C++-, Python- und Java-Implementierungen starten mit einem Einheitsdreieck mit Ecken \((0,0)\), \((1,0)\) und \((1/2,\sqrt{3}/2)\). Die Mittelpunkte seiner Seiten legen die Hilfsfamilien mit Winkeln \(\pm 30^\circ\) sowie die vertikale Familie fest, und ganzzahlige oder halbganzzahlige Verschiebungen erzeugen alle Geraden für die Größe \(n\).
Darum ist die gesamte Konstruktion so regelmäßig: Es gibt nur sechs Prototyp-Richtungen, die über die Figur verschoben werden, bis jede Trägergerade der Schraffur erzeugt ist.
Für jedes Geradenpaar löst die Implementierung ein lineares \(2\times 2\)-System. Parallele Paare fallen sofort durch den Determinantentest heraus. Nichtparallele Paare werden anschließend über die drei Orientierungsungleichungen des äußeren Dreiecks gefiltert, sodass nur Eckpunkte in der Figur erhalten bleiben.
Das Ergebnis ist eine Nachschlagetabelle für Geradenpaare. Spätere Phasen berechnen keinen Schnittpunkt mehr neu, sondern fragen nur noch ab, ob ein Paar einen gültigen Eckpunkt besitzt und wie dieser lautet.
Im letzten Schritt werden alle \(i<j<k\) geprüft. Ein Tripel zählt genau dann, wenn die drei gespeicherten Paar-Schnittpunkte \((i,j)\), \((i,k)\) und \((j,k)\) alle gültig sind und keine zwei davon numerisch zusammenfallen.
Dafür wird eine kleine Gleitkomma-Toleranz verwendet, weil sämtliche Koordinaten aus rationalen Zahlen und \(\sqrt{3}\) bestehen und daher nicht exakt binär darstellbar sind. Zusätzlich prüfen die Implementierungen die Geometrie an den kleinen Fällen \(n=1\to 16\) und \(n=2\to 104\), bevor der eigentliche Fall gezählt wird.
Sei \(M=9n-3\) die Zahl der erzeugten Geraden. Die Vorverarbeitung aller Paare kostet \(O(M^2)\), und die eigentliche Dreieckszählung betrachtet alle \(\binom{M}{3}\) Tripel. Insgesamt ergibt sich also
$$O(M^3)=O(n^3).$$
Der Speicherbedarf der Paartabelle ist
$$O(M^2)=O(n^2).$$
Für den konkreten Eingabewert \(n=36\) gilt \(M=321\), also nur \(\binom{321}{2}=51360\) Geradenpaare und \(\binom{321}{3}=5461280\) Geradentripel. Diese Größenordnungen sind klein genug, dass vollständige geometrische Enumeration problemlos praktikabel ist.
Problemin verdiği cross-hatched düzenle bölünmüş, kenar uzunluğu \(n\) olan eşkenar üçgende, kenarları çizilmiş parçalar üzerinde duran bütün üçgenler sayılır. Project Euler sorusunda istenen durum \(n=36\)'dır.
Çözüm, üçgenleri şekillerine göre sınıflandırmaz. Bunun yerine tüm resmi sonlu bir taşıyıcı doğru düzenine çevirir ve bu doğrulardan hangilerinin üçlüler halinde dış kabuğun içinde gerçekten bir üçgen sınırı oluşturduğunu sayar.
Türetim tamamen geometriktir. Cross-hatching deseni açık doğru aileleri olarak yazıldıktan sonra problem şu hale gelir: üretilen doğruların üçlüleri arasında, büyük üçgenin içinde kalan ve tek bir noktada çakışmayan üç çiftli kesişim üreten kaç tane üçlü vardır?
Şunu tanımlayalım:
$$h=\frac{\sqrt{3}}{2},\qquad A=(0,0),\qquad B=(n,0),\qquad C=\left(\frac{n}{2},nh\right).$$
Böylece dış şekil standart bir eşkenar üçgen olarak yerleştirilmiş olur. Bir \(P\) noktası, tam ve ancak yönlü \(AB\), \(BC\) ve \(CA\) kenarlarının sol tarafında kalıyorsa içerde veya sınır üzerindedir. Yönlü alan determinantı
$$\det(P,Q,R)=(Q_x-P_x)(R_y-P_y)-(Q_y-P_y)(R_x-P_x)$$
ile içerde olma testi
$$\det(A,B,P)\ge 0,\qquad \det(B,C,P)\ge 0,\qquad \det(C,A,P)\ge 0$$
şeklindedir. Aynı şey bu koordinatlarda
$$y\ge 0,\qquad y\le \sqrt{3}\,x,\qquad y\le \sqrt{3}\,(n-x)$$
eşitsizliklerine denktir.
Koddaki asıl gözlem şudur: çizilmiş her parça yalnızca altı doğrultudan birine aittir; yatay, düşey, \(\pm 60^\circ\) ve \(\pm 30^\circ\). Her parçayı üzerinde bulunduğu sonsuz doğruya uzatırsak aileler
$$\begin{aligned} y &= kh, && 0\le k\le n-1,\\ x-\sqrt{3}\,y &= s, && -(n-1)\le s\le n-1,\\ x-\frac{y}{\sqrt{3}} &= k, && 0\le k\le n-1,\\ x+\frac{y}{\sqrt{3}} &= k+1, && 0\le k\le n-1,\\ x+\sqrt{3}\,y &= t, && 1\le t\le 2n-1,\\ x &= \frac{u}{2}, && 1\le u\le 2n-1 \end{aligned}$$
olur. Bu ailelerin büyüklükleri
$$n,\quad 2n-1,\quad n,\quad n,\quad 2n-1,\quad 2n-1$$
olduğu için toplam taşıyıcı doğru sayısı
$$M=n+(2n-1)+n+n+(2n-1)+(2n-1)=9n-3$$
çıkar. \(n=36\) için bu sayı yalnızca \(321\)'dir. Asıl sadeleştirme budur: karmaşık görünen şekil, aslında orta büyüklükte bir doğru düzenine indirgenir.
Her doğru
$$ax+by=c$$
biçiminde tutulur. \(P=(p_x,p_y)\) ve \(Q=(q_x,q_y)\) noktalarından geçen doğru için
$$a=p_y-q_y,\qquad b=q_x-p_x,\qquad c=q_xp_y-p_xq_y$$
kullanılır. İki doğru \((a_1,b_1,c_1)\) ve \((a_2,b_2,c_2)\) için
$$\Delta=a_1b_2-a_2b_1$$
olsun. \(\Delta=0\) ise doğrular paraleldir. Aksi halde tek kesişim noktası
$$x=\frac{c_1b_2-c_2b_1}{\Delta},\qquad y=\frac{a_1c_2-a_2c_1}{\Delta}$$
formülüyle bulunur. Bu nokta dış kabuğun dışında kalıyorsa hemen atılır. Böylece her sırasız doğru çifti için ya geçerli bir iç köşe vardır ya da hiç yoktur.
Üretilmiş üç doğru \(\ell_1,\ell_2,\ell_3\) alalım. Eğer bir çift paralelse bir köşe eksiktir ve üçgen oluşmaz.
Üç çift kesişimin hepsi var ama bunlardan ikisi aynıysa, üç doğru aynı noktada buluşuyordur; sınır tek noktada çökerek dejenere olur.
Üç çift kesişim de varsa ve üçü de farklıysa, bu üç nokta tam olarak bir üçgenin köşeleridir ve kenarlar \(\ell_1,\ell_2,\ell_3\) üzerinde yatar.
Tersi de doğrudur: desendeki her üçgenin üç kenarı, yukarıdaki listede bulunan üç benzersiz taşıyıcı doğru üzerinde bulunur. Bu yüzden geçerli doğru üçlülerini saymak, her üçgeni tam bir kez saymak demektir.
\(n=1\) olduğunda altı aile tam olarak şu altı doğruyu verir:
$$y=0,\quad x-\sqrt{3}\,y=0,\quad x-\frac{y}{\sqrt{3}}=0,\quad x+\frac{y}{\sqrt{3}}=1,\quad x+\sqrt{3}\,y=1,\quad x=\frac{1}{2}.$$
Şu üçlüyü seçelim:
$$y=0,\qquad x=\frac{1}{2},\qquad x+\sqrt{3}\,y=1.$$
Çiftli kesişimler
$$\left(\frac{1}{2},0\right),\qquad (1,0),\qquad \left(\frac{1}{2},\frac{1}{2\sqrt{3}}\right)$$
olur; bunlar dış kabuğun içinde bulunan üç farklı noktadır, dolayısıyla bu üçlü bir üçgen sayılır.
Buna karşılık
$$y=0,\qquad x-\frac{y}{\sqrt{3}}=0,\qquad x-\sqrt{3}\,y=0$$
üçlüsünün bütün çiftli kesişimleri \(A=(0,0)\) noktasında çakışır ve bu yüzden reddedilir. Toplam \(\binom{6}{3}=20\) üçlü arasında 16 geçerli üçgen kalması, uygulamaların kullandığı ilk kontrol noktasıyla aynıdır.
C++, Python ve Java uygulamaları önce köşeleri \((0,0)\), \((1,0)\) ve \((1/2,\sqrt{3}/2)\) olan birim eşkenar üçgeni alır. Kenar orta noktaları, \(\pm 30^\circ\) doğrularını ve düşey yardımcı aileyi belirler; ardından tam sayı ve yarım tam sayı kaydırmalarla büyüklüğü \(n\) olan bütün gerekli doğrular üretilir.
Bu yüzden doğru listesi son derece düzenlidir: aslında yalnızca altı prototip yön vardır ve bunlar tüm şekil üzerinde kaydırılarak desendeki bütün taşıyıcı doğrular elde edilir.
Her doğru çifti için uygulama bir \(2\times 2\) lineer sistem çözer. Paralel çiftler determinant testinde anında elenir. Paralel olmayan çiftler ise dış üçgenin üç yönlü alan eşitsizliği ile süzülür; böylece yalnızca gerçekten şeklin içinde kalan köşeler tutulur.
Sonuç, doğru çiftleriyle indekslenen bir tablo olur. Sonraki aşamalarda hiçbir kesişim yeniden hesaplanmaz; yalnızca bir çiftin geçerli köşesi olup olmadığı ve varsa koordinatı okunur.
Son aşama bütün \(i<j<k\) üçlülerini gezer. Bir üçlü tam ve ancak \((i,j)\), \((i,k)\) ve \((j,k)\) çiftleri için saklanan üç kesişim de geçerliyse ve bu üç noktadan hiçbiri sayısal olarak aynı değilse katkı yapar.
Koordinatlarda hem rasyonel değerler hem de \(\sqrt{3}\) bulunduğu için küçük bir kayan nokta toleransı kullanılır; tam ikili aritmetik burada mümkün değildir. Uygulamalar ayrıca ana duruma geçmeden önce \(n=1\to 16\) ve \(n=2\to 104\) küçük vakalarını doğrular.
\(M=9n-3\) üretilen doğru sayısı olsun. Bütün çiftlerin ön işlenmesi \(O(M^2)\), üçgen sayımı için bütün \(\binom{M}{3}\) üçlülerin denenmesi ise \(O(M^3)\) zaman gerektirir. Dolayısıyla toplam süre
$$O(M^3)=O(n^3)$$
olur. Çift tablosunun bellek maliyeti ise
$$O(M^2)=O(n^2)$$
dir. Gerçek girdi olan \(n=36\) için \(M=321\), yani yalnızca \(\binom{321}{2}=51360\) doğru çifti ve \(\binom{321}{3}=5461280\) doğru üçlüsü vardır. Bu boyutlar tam geometrik taramayı rahatlıkla uygulanabilir kılar.
Se parte de un triángulo equilátero de lado \(n\), subdividido con el patrón cross-hatched del enunciado, y hay que contar todos los triángulos cuyas tres aristas coinciden con segmentos dibujados. En el problema de Project Euler, \(n=36\).
Las implementaciones no intentan clasificar los triángulos por forma. Lo que hacen es convertir toda la figura en una disposición finita de rectas soporte y contar qué ternas de esas rectas delimitan realmente un triángulo dentro del contorno exterior.
La derivación es geométrica, no recursiva. Una vez escritas de forma explícita las familias de rectas del tramado, la pregunta pasa a ser: entre todas las ternas de rectas generadas, ¿cuántas producen tres intersecciones por pares que están dentro del gran triángulo y no colapsan en un único punto?
Definimos
$$h=\frac{\sqrt{3}}{2},\qquad A=(0,0),\qquad B=(n,0),\qquad C=\left(\frac{n}{2},nh\right).$$
Con esto, la figura exterior queda como un triángulo equilátero estándar. Un punto \(P\) está dentro o sobre el borde exactamente cuando queda a la izquierda de las aristas orientadas \(AB\), \(BC\) y \(CA\). Usando el determinante de área orientada
$$\det(P,Q,R)=(Q_x-P_x)(R_y-P_y)-(Q_y-P_y)(R_x-P_x),$$
la condición de pertenencia es
$$\det(A,B,P)\ge 0,\qquad \det(B,C,P)\ge 0,\qquad \det(C,A,P)\ge 0.$$
En estas coordenadas eso equivale a
$$y\ge 0,\qquad y\le \sqrt{3}\,x,\qquad y\le \sqrt{3}\,(n-x).$$
El código deja claro que cada segmento dibujado pertenece a una de solo seis direcciones: horizontal, vertical, \(\pm 60^\circ\) y \(\pm 30^\circ\). Si prolongamos cada segmento hasta su recta soporte completa, las familias quedan
$$\begin{aligned} y &= kh, && 0\le k\le n-1,\\ x-\sqrt{3}\,y &= s, && -(n-1)\le s\le n-1,\\ x-\frac{y}{\sqrt{3}} &= k, && 0\le k\le n-1,\\ x+\frac{y}{\sqrt{3}} &= k+1, && 0\le k\le n-1,\\ x+\sqrt{3}\,y &= t, && 1\le t\le 2n-1,\\ x &= \frac{u}{2}, && 1\le u\le 2n-1. \end{aligned}$$
Sus tamaños son
$$n,\quad 2n-1,\quad n,\quad n,\quad 2n-1,\quad 2n-1,$$
así que el número total de rectas soporte es
$$M=n+(2n-1)+n+n+(2n-1)+(2n-1)=9n-3.$$
Para \(n=36\), esto da solo \(M=321\) rectas. Ésa es la reducción decisiva: una figura visualmente muy cargada se convierte en una disposición finita de tamaño moderado.
Cada recta se guarda en la forma
$$ax+by=c.$$
Si la recta pasa por \(P=(p_x,p_y)\) y \(Q=(q_x,q_y)\), se usan
$$a=p_y-q_y,\qquad b=q_x-p_x,\qquad c=q_xp_y-p_xq_y.$$
Para dos rectas \((a_1,b_1,c_1)\) y \((a_2,b_2,c_2)\), definimos
$$\Delta=a_1b_2-a_2b_1.$$
Si \(\Delta=0\), son paralelas. En caso contrario, su intersección única es
$$x=\frac{c_1b_2-c_2b_1}{\Delta},\qquad y=\frac{a_1c_2-a_2c_1}{\Delta}.$$
Si ese punto cae fuera del triángulo exterior, se descarta inmediatamente. Después de este preproceso, cada par no ordenado de rectas queda marcado como inválido o asociado a un vértice concreto dentro de la figura.
Tomemos tres rectas generadas \(\ell_1,\ell_2,\ell_3\). Si alguna pareja es paralela, falta un vértice y no hay triángulo.
Si existen las tres intersecciones por pares, pero dos coinciden, entonces las tres rectas concurren en un mismo punto y la supuesta frontera degenera.
Si las tres intersecciones existen y son puntos distintos, esos tres puntos son los vértices de un único triángulo cuyas aristas reposan sobre \(\ell_1,\ell_2,\ell_3\).
La recíproca también vale: todo triángulo del dibujo tiene sus tres lados sobre tres rectas soporte únicas de la lista anterior. Por eso contar ternas válidas de rectas equivale a contar cada triángulo exactamente una vez.
Cuando \(n=1\), las seis familias producen exactamente estas seis rectas:
$$y=0,\quad x-\sqrt{3}\,y=0,\quad x-\frac{y}{\sqrt{3}}=0,\quad x+\frac{y}{\sqrt{3}}=1,\quad x+\sqrt{3}\,y=1,\quad x=\frac{1}{2}.$$
Si elegimos
$$y=0,\qquad x=\frac{1}{2},\qquad x+\sqrt{3}\,y=1,$$
las intersecciones por pares son
$$\left(\frac{1}{2},0\right),\qquad (1,0),\qquad \left(\frac{1}{2},\frac{1}{2\sqrt{3}}\right),$$
tres puntos distintos dentro del contorno. Esa terna aporta, por tanto, un triángulo.
En cambio, la terna
$$y=0,\qquad x-\frac{y}{\sqrt{3}}=0,\qquad x-\sqrt{3}\,y=0$$
queda descartada porque todas sus intersecciones por pares coinciden en \(A=(0,0)\). Al aplicar esta prueba a las \(\binom{6}{3}=20\) ternas posibles, sobreviven 16 triángulos, exactamente el primer valor de verificación de las implementaciones.
Las implementaciones en C++, Python y Java parten de un triángulo equilátero unitario con vértices \((0,0)\), \((1,0)\) y \((1/2,\sqrt{3}/2)\). Los puntos medios de sus lados fijan las familias auxiliares de \(\pm 30^\circ\) y la familia vertical, y luego traslaciones enteras o semienteras generan todas las rectas necesarias para tamaño \(n\).
Por eso la lista de rectas es tan regular: en realidad solo existen seis direcciones prototipo, desplazadas a lo largo de la figura hasta cubrir todo el patrón cross-hatched.
Para cada par de rectas, la implementación resuelve un sistema lineal \(2\times 2\). Las parejas paralelas se rechazan con la prueba del determinante. Las no paralelas pasan después por las tres desigualdades de orientación del triángulo exterior, de modo que solo sobreviven vértices realmente situados en la figura.
El resultado es una tabla indexada por pares de rectas. Las fases posteriores no vuelven a calcular intersecciones; solo consultan si una pareja tiene un vértice válido y cuál es ese punto.
La fase final recorre todos los \(i<j<k\). Una terna cuenta exactamente cuando las tres intersecciones almacenadas \((i,j)\), \((i,k)\) y \((j,k)\) son válidas y ningún par de esos puntos coincide numéricamente.
Se usa una pequeña tolerancia de coma flotante porque las coordenadas involucran números racionales y \(\sqrt{3}\), así que no hay aritmética binaria exacta. Además, las implementaciones comprueban primero los casos pequeños \(n=1\to 16\) y \(n=2\to 104\) antes de atacar el caso principal.
Sea \(M=9n-3\) el número de rectas generadas. El preproceso de pares cuesta \(O(M^2)\), y el recuento principal examina todas las \(\binom{M}{3}\) ternas. El tiempo total es, por tanto,
$$O(M^3)=O(n^3).$$
La tabla de pares requiere
$$O(M^2)=O(n^2)$$
de memoria. Para el valor real \(n=36\), se obtiene \(M=321\), es decir, solo \(\binom{321}{2}=51360\) pares de rectas y \(\binom{321}{3}=5461280\) ternas. Ese tamaño hace perfectamente viable una enumeración geométrica exhaustiva.
题目给出一个边长为 \(n\) 的等边三角形，并按 cross-hatched 的方式画出内部线段。要求统计所有边都落在已画线段上的三角形。Project Euler 的实际数据是 \(n=36\)。
实现并没有按“大小”或“朝向”去分类三角形，而是把整幅图转写成一个有限的直线排列，然后判断哪些直线三元组会在外层大三角内部真正围出一个三角形。
这个解法的核心是几何建模，而不是递推。只要把 cross-hatched 图案对应的所有直线族明确写出来，问题就变成：在所有生成出的直线三元组中，有多少组会产生三个两两交点，并且这三个交点都在外层三角形内部，且不会退化成同一个点？
设
$$h=\frac{\sqrt{3}}{2},\qquad A=(0,0),\qquad B=(n,0),\qquad C=\left(\frac{n}{2},nh\right).$$
这样外框就是标准的等边三角形。点 \(P\) 在内部或边界上的充要条件，是它位于有向边 \(AB\)、\(BC\)、\(CA\) 的左侧。用有向面积行列式
$$\det(P,Q,R)=(Q_x-P_x)(R_y-P_y)-(Q_y-P_y)(R_x-P_x)$$
来写，内部判定就是
$$\det(A,B,P)\ge 0,\qquad \det(B,C,P)\ge 0,\qquad \det(C,A,P)\ge 0.$$
在这组坐标下，它也等价于
$$y\ge 0,\qquad y\le \sqrt{3}\,x,\qquad y\le \sqrt{3}\,(n-x).$$
从代码里可以直接看出，所有已画线段只属于六种方向：水平、竖直、\(\pm 60^\circ\) 和 \(\pm 30^\circ\)。把每条线段延长成其所在的整条支撑直线之后，这六族可以写成
$$\begin{aligned} y &= kh, && 0\le k\le n-1,\\ x-\sqrt{3}\,y &= s, && -(n-1)\le s\le n-1,\\ x-\frac{y}{\sqrt{3}} &= k, && 0\le k\le n-1,\\ x+\frac{y}{\sqrt{3}} &= k+1, && 0\le k\le n-1,\\ x+\sqrt{3}\,y &= t, && 1\le t\le 2n-1,\\ x &= \frac{u}{2}, && 1\le u\le 2n-1. \end{aligned}$$
它们的条数分别是
$$n,\quad 2n-1,\quad n,\quad n,\quad 2n-1,\quad 2n-1,$$
因此总直线数为
$$M=n+(2n-1)+n+n+(2n-1)+(2n-1)=9n-3.$$
当 \(n=36\) 时，只有 \(M=321\) 条支撑直线。这就是整道题的关键压缩：图形表面上很复杂，但真正需要处理的对象只是一个中等规模的直线集合。
每条直线都以
$$ax+by=c$$
的形式存储。若直线经过 \(P=(p_x,p_y)\) 和 \(Q=(q_x,q_y)\)，则系数取为
$$a=p_y-q_y,\qquad b=q_x-p_x,\qquad c=q_xp_y-p_xq_y.$$
对于两条直线 \((a_1,b_1,c_1)\) 和 \((a_2,b_2,c_2)\)，定义
$$\Delta=a_1b_2-a_2b_1.$$
如果 \(\Delta=0\)，说明两线平行，没有唯一交点。否则交点坐标就是
$$x=\frac{c_1b_2-c_2b_1}{\Delta},\qquad y=\frac{a_1c_2-a_2c_1}{\Delta}.$$
如果该点落在外层三角形之外，就立刻丢弃。经过这一步预处理后，每一对无序直线要么没有可用顶点，要么对应外框内部的一个确定交点。
取三条生成出的直线 \(\ell_1,\ell_2,\ell_3\)。如果其中某一对平行，那么至少缺少一个顶点，不可能形成三角形。
如果三组两两交点都存在，但其中有两个交点重合，那么三条直线其实共点，边界发生退化，不是一个真正的三角形。
只有当三组两两交点全部存在，而且三点互不相同时，它们才构成唯一一个三角形，三条边分别落在 \(\ell_1,\ell_2,\ell_3\) 上。
反过来，图中的每一个三角形也一定有三条唯一的支撑直线，且它们都来自上面的六族。所以，统计有效直线三元组，就等价于把每个三角形恰好数一次。
当 \(n=1\) 时，六个方向族只产生六条直线：
$$y=0,\quad x-\sqrt{3}\,y=0,\quad x-\frac{y}{\sqrt{3}}=0,\quad x+\frac{y}{\sqrt{3}}=1,\quad x+\sqrt{3}\,y=1,\quad x=\frac{1}{2}.$$
选取
$$y=0,\qquad x=\frac{1}{2},\qquad x+\sqrt{3}\,y=1$$
这三条线，它们的两两交点为
$$\left(\frac{1}{2},0\right),\qquad (1,0),\qquad \left(\frac{1}{2},\frac{1}{2\sqrt{3}}\right),$$
是三个位于外框内的不同点，因此它们贡献一个三角形。
相反，三条线
$$y=0,\qquad x-\frac{y}{\sqrt{3}}=0,\qquad x-\sqrt{3}\,y=0$$
的所有两两交点都落在 \(A=(0,0)\)，因此必须作为退化情形删除。把这个判定应用到全部 \(\binom{6}{3}=20\) 个三元组后，恰好剩下 16 个三角形，这与实现里的第一个校验值完全一致。
C++、Python 和 Java 实现都先从一个单位等边三角形出发，其顶点是 \((0,0)\)、\((1,0)\)、\((1/2,\sqrt{3}/2)\)。边中点决定了 \(\pm 30^\circ\) 的辅助直线族以及竖直直线族，然后再通过整数和平移半单位的方式，把所有大小为 \(n\) 时需要的直线全部生成出来。
这就是为什么直线表会如此规则：本质上只有六种原型方向，程序只是把它们沿着整张图依次平移。
对每一对直线，程序都解一个 \(2\times 2\) 线性系统。平行对会被行列式测试直接淘汰。非平行对再经过外层三角形的三个有向面积不等式过滤，只有真正落在图形内部的交点才保留下来。
于是得到一张以“直线对”为索引的查表结构。后面的步骤不再重新算交点，只需要查询某一对是否有有效顶点，以及该顶点坐标是什么。
最后一层遍历所有 \(i<j<k\)。一组直线只有在 \((i,j)\)、\((i,k)\)、\((j,k)\) 这三个已缓存交点都有效，且三点之间没有任何两个在数值上相同的时候，才会贡献一个三角形。
因为坐标同时包含有理数和 \(\sqrt{3}\)，实现使用了很小的浮点容差来判断“两点是否相同”；这里无法依赖严格的二进制精确计算。实现还会先检查小规模结果 \(n=1\to 16\) 与 \(n=2\to 104\)，确认几何模型无误后再处理主问题。
记生成的直线总数为 \(M=9n-3\)。预处理所有线对需要 \(O(M^2)\) 时间，而主体计数需要检查全部 \(\binom{M}{3}\) 个三元组，因此总时间复杂度为
$$O(M^3)=O(n^3).$$
线对缓存表的空间复杂度为
$$O(M^2)=O(n^2).$$
对实际输入 \(n=36\) 而言，\(M=321\)，也就是只有 \(\binom{321}{2}=51360\) 个线对和 \(\binom{321}{3}=5461280\) 个线三元组。这个规模足够小，完全可以直接做穷举式几何统计。
Дан равносторонний треугольник со стороной \(n\), разбитый в cross-hatched стиле из условия. Нужно посчитать все треугольники, чьи стороны целиком лежат на проведенных отрезках. В самой задаче Project Euler используется \(n=36\).
Реализации не пытаются разбирать треугольники по типам или размерам. Вместо этого весь рисунок заменяется конечным набором опорных прямых, после чего считается, какие тройки этих прямых действительно образуют треугольник внутри внешней оболочки.
Здесь нужен именно геометрический вывод, а не рекуррентные соотношения. Как только все семейства прямых в рисунке выписаны явно, задача сводится к вопросу: сколько троек сгенерированных прямых дают три попарных пересечения, лежащих внутри большого треугольника и не сливающихся в одну точку?
Положим
$$h=\frac{\sqrt{3}}{2},\qquad A=(0,0),\qquad B=(n,0),\qquad C=\left(\frac{n}{2},nh\right).$$
Так внешний контур становится стандартным равносторонним треугольником. Точка \(P\) лежит внутри или на границе тогда и только тогда, когда она находится слева от ориентированных сторон \(AB\), \(BC\) и \(CA\). Если использовать ориентированный определитель площади
$$\det(P,Q,R)=(Q_x-P_x)(R_y-P_y)-(Q_y-P_y)(R_x-P_x),$$
то условие принадлежности записывается как
$$\det(A,B,P)\ge 0,\qquad \det(B,C,P)\ge 0,\qquad \det(C,A,P)\ge 0.$$
В этих координатах это эквивалентно системе
$$y\ge 0,\qquad y\le \sqrt{3}\,x,\qquad y\le \sqrt{3}\,(n-x).$$
Из кода видно, что каждый проведенный отрезок относится лишь к одному из шести направлений: горизонтальному, вертикальному, \(\pm 60^\circ\) или \(\pm 30^\circ\). Если продолжить каждый отрезок до всей его несущей прямой, получаются семейства
$$\begin{aligned} y &= kh, && 0\le k\le n-1,\\ x-\sqrt{3}\,y &= s, && -(n-1)\le s\le n-1,\\ x-\frac{y}{\sqrt{3}} &= k, && 0\le k\le n-1,\\ x+\frac{y}{\sqrt{3}} &= k+1, && 0\le k\le n-1,\\ x+\sqrt{3}\,y &= t, && 1\le t\le 2n-1,\\ x &= \frac{u}{2}, && 1\le u\le 2n-1. \end{aligned}$$
Число прямых в этих семействах равно
$$n,\quad 2n-1,\quad n,\quad n,\quad 2n-1,\quad 2n-1,$$
поэтому всего получаем
$$M=n+(2n-1)+n+n+(2n-1)+(2n-1)=9n-3$$
опорных прямых. Для \(n=36\) это всего \(321\) прямые. Именно это и делает задачу выполнимой: сложный рисунок сводится к конечной конфигурации умеренного размера.
Каждая прямая хранится в виде
$$ax+by=c.$$
Если прямая проходит через точки \(P=(p_x,p_y)\) и \(Q=(q_x,q_y)\), то используются коэффициенты
$$a=p_y-q_y,\qquad b=q_x-p_x,\qquad c=q_xp_y-p_xq_y.$$
Для двух прямых \((a_1,b_1,c_1)\) и \((a_2,b_2,c_2)\) вводится
$$\Delta=a_1b_2-a_2b_1.$$
Если \(\Delta=0\), прямые параллельны. Иначе их единственная точка пересечения равна
$$x=\frac{c_1b_2-c_2b_1}{\Delta},\qquad y=\frac{a_1c_2-a_2c_1}{\Delta}.$$
Если эта точка находится вне внешнего треугольника, она сразу отбрасывается. После такого препроцессинга каждая неупорядоченная пара прямых либо не дает допустимой вершины, либо дает одну конкретную вершину внутри фигуры.
Возьмем три сгенерированные прямые \(\ell_1,\ell_2,\ell_3\). Если какая-то пара параллельна, хотя бы одной вершины не существует, значит, треугольника нет.
Если все три попарных пересечения существуют, но две из этих точек совпадают, то три прямые проходят через одну точку, и граница вырождается.
Если же все три попарных пересечения существуют и все три различны, то они образуют вершины ровно одного треугольника, стороны которого лежат на \(\ell_1,\ell_2,\ell_3\).
Обратное тоже верно: любой треугольник в рисунке имеет три стороны на трех уникальных опорных прямых из перечисленного набора. Поэтому подсчет допустимых троек прямых считает каждый треугольник ровно один раз.
При \(n=1\) шесть семейств дают ровно шесть прямых:
$$y=0,\quad x-\sqrt{3}\,y=0,\quad x-\frac{y}{\sqrt{3}}=0,\quad x+\frac{y}{\sqrt{3}}=1,\quad x+\sqrt{3}\,y=1,\quad x=\frac{1}{2}.$$
Выберем
$$y=0,\qquad x=\frac{1}{2},\qquad x+\sqrt{3}\,y=1.$$
Их попарные пересечения равны
$$\left(\frac{1}{2},0\right),\qquad (1,0),\qquad \left(\frac{1}{2},\frac{1}{2\sqrt{3}}\right),$$
то есть это три различные точки внутри оболочки. Такая тройка действительно дает один треугольник.
А вот тройка
$$y=0,\qquad x-\frac{y}{\sqrt{3}}=0,\qquad x-\sqrt{3}\,y=0$$
вырождена, потому что все три попарных пересечения совпадают в точке \(A=(0,0)\). Если проверить так все \(\binom{6}{3}=20\) троек, останется 16 треугольников, что совпадает с первой контрольной проверкой в реализациях.
Реализации на C++, Python и Java стартуют с единичного равностороннего треугольника с вершинами \((0,0)\), \((1,0)\) и \((1/2,\sqrt{3}/2)\). Середины его сторон задают вспомогательные семейства под углами \(\pm 30^\circ\) и вертикальное семейство, а затем с помощью целых и полуцелых сдвигов генерируются все прямые для размера \(n\).
Именно поэтому список прямых получается настолько регулярным: по сути есть лишь шесть базовых направлений, которые просто сдвигаются по всей фигуре.
Для каждой пары прямых программа решает одно линейное уравнение размера \(2\times 2\). Параллельные пары сразу отбрасываются проверкой определителя. Непараллельные пары затем фильтруются тремя ориентационными неравенствами внешнего треугольника, так что сохраняются только вершины, реально лежащие внутри рисунка.
В результате получается таблица, индексируемая парами прямых. На поздних этапах пересечения уже не пересчитываются, а только считываются из этой таблицы.
Финальный проход рассматривает все \(i<j<k\). Тройка дает вклад тогда и только тогда, когда пересечения \((i,j)\), \((i,k)\) и \((j,k)\) существуют и никакие две из этих точек не совпадают численно.
Используется малая плавающая погрешность, потому что координаты содержат рациональные числа и \(\sqrt{3}\), а значит, точная двоичная арифметика недоступна. Перед основным подсчетом реализации также проверяют маленькие случаи \(n=1\to 16\) и \(n=2\to 104\).
Пусть \(M=9n-3\) — число сгенерированных прямых. Предобработка всех пар требует \(O(M^2)\), а основной подсчет просматривает все \(\binom{M}{3}\) троек, так что полное время работы равно
$$O(M^3)=O(n^3).$$
Память на таблицу пар составляет
$$O(M^2)=O(n^2).$$
Для реального значения \(n=36\) имеем \(M=321\), то есть только \(\binom{321}{2}=51360\) пар прямых и \(\binom{321}{3}=5461280\) троек прямых. Такой масштаб вполне позволяет прямой полный геометрический перебор.
نبدأ بمثلث متساوي الأضلاع طول ضلعه \(n\)، مرسوم بداخله النمط cross-hatched كما في نص المسألة، ثم نعدّ كل مثلث تقع أضلاعه الثلاثة على مقاطع مرسومة فعلًا. في مسألة Project Euler المطلوبة تكون القيمة \(n=36\).
التنفيذ لا يصنف المثلثات حسب الحجم أو الاتجاه. بدلًا من ذلك يحوّل الرسم كله إلى ترتيب منتهٍ من المستقيمات الحاملة، ثم يفحص أي ثلاثية من هذه المستقيمات تُكوّن فعلًا مثلثًا داخل الغلاف الخارجي.
الفكرة الأساسية هنا هندسية وليست علاقة عودية. بعد كتابة جميع عائلات المستقيمات التي يولدها النمط بشكل صريح، تصبح المسألة: كم عدد ثلاثيات المستقيمات التي تعطي ثلاث نقاط تقاطع ثنائية داخل المثلث الكبير، على ألا تنهار هذه النقاط إلى نقطة واحدة مشتركة؟
نضع
$$h=\frac{\sqrt{3}}{2},\qquad A=(0,0),\qquad B=(n,0),\qquad C=\left(\frac{n}{2},nh\right).$$
بهذا نحصل على تمثيل قياسي للمثلث المتساوي الأضلاع الخارجي. تكون النقطة \(P\) داخل الشكل أو على حدّه إذا وفقط إذا كانت على يسار الأضلاع الموجهة \(AB\) و\(BC\) و\(CA\). وباستخدام محدد المساحة الموجهة
$$\det(P,Q,R)=(Q_x-P_x)(R_y-P_y)-(Q_y-P_y)(R_x-P_x),$$
فإن اختبار الانتماء هو
$$\det(A,B,P)\ge 0,\qquad \det(B,C,P)\ge 0,\qquad \det(C,A,P)\ge 0.$$
وهذا يكافئ في هذا الإحداثي المتراجحات
$$y\ge 0,\qquad y\le \sqrt{3}\,x,\qquad y\le \sqrt{3}\,(n-x).$$
من قراءة الشيفرة يتبين أن كل مقطع مرسوم ينتمي إلى واحد من ستة اتجاهات فقط: أفقي، عمودي، \(\pm 60^\circ\)، و\(\pm 30^\circ\). وإذا مددنا كل مقطع إلى المستقيم الكامل الحامل له، نحصل على العائلات
$$\begin{aligned} y &= kh, && 0\le k\le n-1,\\ x-\sqrt{3}\,y &= s, && -(n-1)\le s\le n-1,\\ x-\frac{y}{\sqrt{3}} &= k, && 0\le k\le n-1,\\ x+\frac{y}{\sqrt{3}} &= k+1, && 0\le k\le n-1,\\ x+\sqrt{3}\,y &= t, && 1\le t\le 2n-1,\\ x &= \frac{u}{2}, && 1\le u\le 2n-1. \end{aligned}$$
أحجام هذه العائلات هي
$$n,\quad 2n-1,\quad n,\quad n,\quad 2n-1,\quad 2n-1,$$
ولذلك يكون العدد الكلي للمستقيمات الحاملة
$$M=n+(2n-1)+n+n+(2n-1)+(2n-1)=9n-3.$$
وعند \(n=36\) نحصل على \(321\) مستقيمًا فقط. هذه هي الخطوة الحاسمة: الرسم يبدو غنيًا جدًا، لكن كل العدّ يُختزل إلى ترتيب منتهٍ متوسط الحجم من المستقيمات.
يُخزن كل مستقيم بالشكل
$$ax+by=c.$$
وإذا مر المستقيم بالنقطتين \(P=(p_x,p_y)\) و\(Q=(q_x,q_y)\)، فإن المعاملات تكون
$$a=p_y-q_y,\qquad b=q_x-p_x,\qquad c=q_xp_y-p_xq_y.$$
ولمستقيمين \((a_1,b_1,c_1)\) و\((a_2,b_2,c_2)\)، نعرف
$$\Delta=a_1b_2-a_2b_1.$$
إذا كانت \(\Delta=0\) فالمستقيمان متوازيان. وإلا فإن نقطة التقاطع الوحيدة هي
$$x=\frac{c_1b_2-c_2b_1}{\Delta},\qquad y=\frac{a_1c_2-a_2c_1}{\Delta}.$$
إذا وقعت هذه النقطة خارج المثلث الخارجي فترفض فورًا. بعد هذه المرحلة يصبح كل زوج غير مرتب من المستقيمات إما غير صالح، أو مرتبطًا برأس واحد محدد داخل الشكل.
خذ ثلاثة مستقيمات مولدة \(\ell_1,\ell_2,\ell_3\). إذا كان أحد الأزواج متوازيًا، فهناك رأس مفقود، وبالتالي لا يوجد مثلث.
وإذا كانت التقاطعات الثلاثة الثنائية موجودة لكن اثنتين منها متطابقتين، فهذا يعني أن المستقيمات الثلاثة متلاقية في نقطة واحدة، فينهار الحد إلى حالة متدهورة.
أما إذا وجدت التقاطعات الثلاثة وكانت نقاطًا مميزة بعضها عن بعض، فهي بالضبط رؤوس مثلث واحد وحيد تقع أضلاعه على \(\ell_1,\ell_2,\ell_3\).
والعكس صحيح أيضًا: كل مثلث في الرسم يمتلك ثلاثة أضلاع على ثلاثة مستقيمات حاملة فريدة من العائلات السابقة. لذلك فإن عدّ ثلاثيات المستقيمات الصالحة يعدّ كل مثلث مرة واحدة فقط.
عندما يكون \(n=1\)، تعطي العائلات الستة هذه المستقيمات الستة بالضبط:
$$y=0,\quad x-\sqrt{3}\,y=0,\quad x-\frac{y}{\sqrt{3}}=0,\quad x+\frac{y}{\sqrt{3}}=1,\quad x+\sqrt{3}\,y=1,\quad x=\frac{1}{2}.$$
لنأخذ الثلاثية
$$y=0,\qquad x=\frac{1}{2},\qquad x+\sqrt{3}\,y=1.$$
فتكون نقاط التقاطع الثنائية
$$\left(\frac{1}{2},0\right),\qquad (1,0),\qquad \left(\frac{1}{2},\frac{1}{2\sqrt{3}}\right),$$
وهي ثلاث نقاط مختلفة داخل الغلاف، لذا تساهم هذه الثلاثية بمثلث واحد.
أما الثلاثية
$$y=0,\qquad x-\frac{y}{\sqrt{3}}=0,\qquad x-\sqrt{3}\,y=0$$
فكل تقاطعاتها الثنائية تقع عند \(A=(0,0)\)، ولذلك تستبعد بوصفها حالة متدهورة. وعند تطبيق هذا المعيار على جميع \(\binom{6}{3}=20\) ثلاثية، يبقى 16 مثلثًا، وهو نفس فحص التحقق الأول في التنفيذات.
تبدأ تطبيقات C++ وPython وJava من مثلث متساوي الأضلاع وحدي الرؤوس \((0,0)\) و\((1,0)\) و\((1/2,\sqrt{3}/2)\). تحدد منتصفات الأضلاع منه عائلات \(\pm 30^\circ\) والعائلة العمودية، ثم تستخدم الإزاحات الصحيحة ونصف الصحيحة لتوليد جميع المستقيمات اللازمة للحجم \(n\).
ولهذا تبدو قائمة المستقيمات منتظمة جدًا: فهناك ستة اتجاهات نموذجية فقط، ويجري إزاحتها عبر الرسم كله حتى تتولد جميع المستقيمات الحاملة للنمط.
لكل زوج من المستقيمات تحلّ الخوارزمية نظامًا خطيًا \(2\times 2\). الأزواج المتوازية تُرفض مباشرة عبر اختبار المحدد. أما الأزواج غير المتوازية فتمر بعد ذلك عبر متراجحات المساحة الموجهة الثلاث الخاصة بالمثلث الخارجي، بحيث لا تبقى إلا الرؤوس الواقعة داخل الشكل فعلًا.
النتيجة جدول مفهرس بأزواج المستقيمات. المراحل اللاحقة لا تعيد حساب أي تقاطع؛ بل تستعلم فقط عما إذا كان الزوج يملك رأسًا صالحًا وما إحداثياته.
المرحلة الأخيرة تمر على جميع \(i<j<k\). تساهم الثلاثية إذا وفقط إذا كانت التقاطعات المخزنة للأزواج \((i,j)\) و\((i,k)\) و\((j,k)\) جميعها صالحة، ولم تكن أي نقطتين من هذه النقاط متطابقتين عدديًا.
يُستخدم هامش خطأ صغير في الحسابات العائمة لأن الإحداثيات مبنية من أعداد نسبية ومن \(\sqrt{3}\)، وبالتالي لا تتوافر دقة ثنائية تامة. كما تتحقق التنفيذات أولًا من القيمتين الصغيرتين \(n=1\to 16\) و\(n=2\to 104\) قبل حساب الحالة الرئيسية.
إذا رمزنا لعدد المستقيمات المولدة بـ \(M=9n-3\)، فإن التحضير الثنائي يحتاج \(O(M^2)\)، بينما يفحص العد الرئيسي جميع \(\binom{M}{3}\) من الثلاثيات، لذا يكون الزمن الكلي
$$O(M^3)=O(n^3).$$
أما الذاكرة اللازمة لجدول الأزواج فهي
$$O(M^2)=O(n^2).$$
وبالنسبة إلى الإدخال الفعلي \(n=36\)، نحصل على \(M=321\)، أي فقط \(\binom{321}{2}=51360\) زوجًا من المستقيمات و\(\binom{321}{3}=5461280\) ثلاثية. هذا الحجم صغير بما يكفي ليكون التعداد الهندسي الكامل عمليًا جدًا.