Let \(O=(0,0)\), and let \(P\) and \(Q\) be distinct lattice points in the square \(0 \le x,y \le 50\), excluding the origin itself. Every unordered pair \(\{P,Q\}\) determines a candidate triangle \(OPQ\). The task is to count how many of those triangles are right triangles.
The C++, Python, and Java implementations do not rely on a closed formula. They use an exact geometric invariant: a right angle is detected by a zero dot product. Because the grid is still small enough, every unordered pair of non-origin lattice points can be tested directly.
Write \(P=(x_1,y_1)\) and \(Q=(x_2,y_2)\). Since the origin is fixed, the whole search space is just the set of unordered pairs of distinct non-origin lattice points. The central question is therefore not how to draw the triangles, but how to recognize efficiently whether a given pair \(\{P,Q\}\) produces a right angle at \(O\), at \(P\), or at \(Q\).
There are \((50+1)^2-1=2600\) lattice points in the square other than the origin. Choosing two of them gives
$$\binom{2600}{2}=3{,}378{,}700$$
candidate triangles. That is too many to reason about one by one by hand, but still small enough for a direct computer sweep. Using unordered pairs is essential, because \(OPQ\) and \(OQP\) are the same triangle.
A non-degenerate triangle can have at most one right angle, so once the three possible vertices have been tested, the decision is complete.
The right angle can occur at exactly one of the three vertices. Using vectors based at the candidate vertex gives three equivalent dot-product tests:
$$\vec{OP}\cdot\vec{OQ}=x_1x_2+y_1y_2=0,$$
$$\vec{PO}\cdot\vec{PQ}=(-x_1,-y_1)\cdot(x_2-x_1,y_2-y_1)=x_1(x_1-x_2)+y_1(y_1-y_2)=0,$$
$$\vec{QO}\cdot\vec{QP}=(-x_2,-y_2)\cdot(x_1-x_2,y_1-y_2)=x_2(x_2-x_1)+y_2(y_2-y_1)=0.$$
These are exactly the three scalar quantities computed by the implementations. Everything is done with integer arithmetic, so there is no floating-point ambiguity and no geometric approximation.
Because all coordinates lie in the first quadrant, every coordinate is nonnegative. Therefore the equation
$$x_1x_2+y_1y_2=0$$
can hold only when one point lies on the positive \(x\)-axis and the other lies on the positive \(y\)-axis. So the right-angle-at-\(O\) triangles contribute exactly \(50^2\) in the full problem, and more generally \(n^2\) on an \(n\times n\) grid.
This observation is not required for the brute-force algorithm, but it is a useful invariant: the origin case is completely characterized by the sign pattern of the coordinates.
If the right angle is at \(P=(x_1,y_1)\), then the segment from \(P\) to \(Q\) must be perpendicular to the segment from \(P\) to the origin. In vector form, \(\vec{PQ}\) must be perpendicular to \(\vec{OP}\). Let
$$g=\gcd(x_1,y_1).$$
A primitive lattice direction perpendicular to \((x_1,y_1)\) is
$$\left(\frac{y_1}{g},-\frac{x_1}{g}\right),$$
and the opposite direction is its negative. So any lattice point \(Q\) producing a right angle at \(P\) must lie on one of the two rays
$$Q=P\pm k\left(\frac{y_1}{g},-\frac{x_1}{g}\right)\qquad (k\in\mathbb{Z}_{>0}),$$
as long as the coordinates stay inside the square \(0 \le x,y \le n\). The same picture, with the roles reversed, explains the right-angle-at-\(Q\) test. The implementation does not march along these rays explicitly, but the dot-product conditions are simply the algebraic form of this perpendicular-line description.
The smallest interesting grid is \(n=2\), where the correct answer is 14. The dot-product viewpoint makes the breakdown easy to see.
There are \(n^2=4\) triangles with the right angle at the origin: choose one point on the \(x\)-axis and one on the \(y\)-axis. There are \(2n^2=8\) more with the right angle on an axis point away from the origin. For example, \(O=(0,0)\), \(P=(1,0)\), and \(Q=(1,1)\) give a right angle at \(P\).
The remaining two come from the interior point \(P=(1,1)\). Here \(g=\gcd(1,1)=1\), so a primitive perpendicular step is \((1,-1)\). Inside the \(2\times2\) square, the valid partners are \(Q=(2,0)\) and \(Q=(0,2)\). For \(Q=(2,0)\),
$$\vec{PO}\cdot\vec{PQ}=(-1,-1)\cdot(1,-1)=0.$$
Thus the total is \(4+8+2=14\). This is exactly the sample value used as a correctness checkpoint in the implementations.
The C++, Python, and Java implementations all follow the same counting strategy. First they enumerate the lattice points in the square and exclude the origin. Then they examine each unordered pair exactly once, either by storing the points in a list first or by iterating over the coordinate grid and skipping pairs that would repeat an earlier triangle.
For each candidate pair, the implementation computes the three dot products corresponding to a right angle at \(O\), at \(P\), and at \(Q\). If at least one of them is zero, the counter is incremented. Because the pair ordering is one-way only, no triangle is counted twice. Because the calculations use integer arithmetic, the test is exact.
The C++ and Java implementations promote the products to 64-bit integers before adding them, which keeps the arithmetic safe even when \(n\) is changed. The Python implementation gets the same safety automatically from Python's integer model.
Let \(M=(n+1)^2-1\) be the number of non-origin lattice points. The algorithm checks all unordered pairs, so the running time is
$$\Theta\!\left(\binom{M}{2}\right)=\Theta(M^2)=\Theta(n^4).$$
For \(n=50\), this means \(3{,}378{,}700\) candidate pairs, and each pair requires only a constant amount of arithmetic. That is why the straightforward method is entirely practical for this problem.
Auxiliary space depends on the implementation style. The direct nested-loop versions use \(O(1)\) extra space beyond the counters, while the version that first materializes the lattice points uses \(O(n^2)\) space for that list. In both cases the memory footprint is small.
Sei \(O=(0,0)\), und seien \(P\) und \(Q\) verschiedene Gitterpunkte im Quadrat \(0 \le x,y \le 50\), wobei der Ursprung selbst ausgeschlossen wird. Jedes ungeordnete Paar \(\{P,Q\}\) bestimmt ein Kandidatendreieck \(OPQ\). Gesucht ist die Anzahl derjenigen Dreiecke, die rechtwinklig sind.
Die C++-, Python- und Java-Implementierungen verwenden keine geschlossene Formel. Sie stutzen sich auf ein exaktes geometrisches Invarianzprinzip: Ein rechter Winkel wird durch ein verschwindendes Skalarprodukt erkannt. Da das Gitter noch klein genug ist, kann jedes ungeordnete Paar von Nicht-Ursprungspunkten direkt getestet werden.
Schreibe \(P=(x_1,y_1)\) und \(Q=(x_2,y_2)\). Weil der Ursprung fest ist, besteht der gesamte Zustandsraum nur aus ungeordneten Paaren verschiedener Gitterpunkte ungleich \(O\). Die zentrale Frage lautet also nicht, wie man Dreiecke zeichnet, sondern wie man fur ein gegebenes Paar \(\{P,Q\}\) effizient erkennt, ob der rechte Winkel bei \(O\), bei \(P\) oder bei \(Q\) liegt.
Im Quadrat gibt es \((50+1)^2-1=2600\) Gitterpunkte auBer dem Ursprung. Wahlen wir zwei davon, erhalten wir
$$\binom{2600}{2}=3{,}378{,}700$$
Kandidatendreiecke. Das ist zu groB fur eine Handrechnung, aber immer noch klein genug fur einen direkten Computer-Durchlauf. Ungeordnete Paare sind entscheidend, weil \(OPQ\) und \(OQP\) dasselbe Dreieck beschreiben.
Ein nicht entartetes Dreieck kann hochstens einen rechten Winkel haben. Sobald also alle drei moglichen Eckpunkte getestet sind, ist die Entscheidung vollstandig.
Der rechte Winkel kann nur an einem der drei Eckpunkte auftreten. Vektoren mit Start am moglichen rechten Winkel liefern drei genaue Skalarprodukt-Tests:
$$\vec{OP}\cdot\vec{OQ}=x_1x_2+y_1y_2=0,$$
$$\vec{PO}\cdot\vec{PQ}=(-x_1,-y_1)\cdot(x_2-x_1,y_2-y_1)=x_1(x_1-x_2)+y_1(y_1-y_2)=0,$$
$$\vec{QO}\cdot\vec{QP}=(-x_2,-y_2)\cdot(x_1-x_2,y_1-y_2)=x_2(x_2-x_1)+y_2(y_2-y_1)=0.$$
Genau diese drei skalaren GroBen werden in den Implementierungen berechnet. Alles bleibt in ganzzahliger Arithmetik; es gibt also weder Rundungsfehler noch geometrische Approximationen.
Da alle Koordinaten im ersten Quadranten liegen, sind sie nichtnegativ. Deshalb kann die Gleichung
$$x_1x_2+y_1y_2=0$$
nur dann gelten, wenn ein Punkt auf der positiven \(x\)-Achse und der andere auf der positiven \(y\)-Achse liegt. Der Beitrag der Dreiecke mit rechtem Winkel in \(O\) ist also im vollen Problem genau \(50^2\), und allgemein \(n^2\) auf einem \(n\times n\)-Gitter.
Fur den Brute-Force-Algorithmus ist diese Beobachtung nicht notwendig, aber sie liefert ein gutes Kontrollargument: Der Ursprungfall ist allein durch das Vorzeichenmuster der Koordinaten vollstandig beschrieben.
Liegt der rechte Winkel bei \(P=(x_1,y_1)\), dann muss die Strecke von \(P\) nach \(Q\) senkrecht zur Strecke von \(P\) zum Ursprung stehen. In Vektorschreibweise bedeutet das: \(\vec{PQ}\) ist orthogonal zu \(\vec{OP}\). Mit
$$g=\gcd(x_1,y_1)$$
ist eine primitive senkrechte Gitterrichtung zu \((x_1,y_1)\)
$$\left(\frac{y_1}{g},-\frac{x_1}{g}\right),$$
und die entgegengesetzte Richtung ist ihr Negatives. Jeder Gitterpunkt \(Q\), der in \(P\) einen rechten Winkel erzeugt, muss also auf einer der beiden Geradenhalbstrahlen liegen:
$$Q=P\pm k\left(\frac{y_1}{g},-\frac{x_1}{g}\right)\qquad (k\in\mathbb{Z}_{>0}),$$
solange die Koordinaten im Quadrat \(0 \le x,y \le n\) bleiben. Dieselbe Beschreibung gilt symmetrisch fur einen rechten Winkel bei \(Q\). Die Implementierung lauft diese Halbstrahlen nicht explizit ab; die Skalarproduktbedingungen sind einfach die algebraische Form dieser senkrechten Geradenbeschreibung.
Das kleinste interessante Gitter ist \(n=2\), und dort lautet die richtige Antwort 14. Die Sicht uber Skalarprodukte macht die Zerlegung transparent.
Es gibt \(n^2=4\) Dreiecke mit rechtem Winkel im Ursprung: Man wahlt einen Punkt auf der \(x\)-Achse und einen auf der \(y\)-Achse. Dazu kommen \(2n^2=8\) Dreiecke mit rechtem Winkel auf einem Achsenpunkt auBerhalb des Ursprungs. Zum Beispiel bilden \(O=(0,0)\), \(P=(1,0)\) und \(Q=(1,1)\) einen rechten Winkel bei \(P\).
Die letzten zwei Dreiecke stammen vom inneren Punkt \(P=(1,1)\). Hier ist \(g=\gcd(1,1)=1\), also ist ein primitiver senkrechter Schritt \((1,-1)\). Innerhalb des \(2\times2\)-Quadrats sind die zulassigen Partner \(Q=(2,0)\) und \(Q=(0,2)\). Fur \(Q=(2,0)\) gilt
$$\vec{PO}\cdot\vec{PQ}=(-1,-1)\cdot(1,-1)=0.$$
Damit ergibt sich insgesamt \(4+8+2=14\). Genau dieser Wert dient in den Implementierungen als Korrektheitskontrolle.
Die C++-, Python- und Java-Implementierungen folgen derselben Zahlstrategie. Zuerst werden die Gitterpunkte im Quadrat erzeugt und der Ursprung ausgeschlossen. Danach wird jedes ungeordnete Paar genau einmal betrachtet, entweder indem die Punkte zuerst in einer Liste gespeichert werden oder indem das Koordinatengitter direkt iteriert wird und spater auftretende Dubletten ubersprungen werden.
Fur jedes Kandidatenpaar berechnet die Implementierung die drei Skalarprodukte fur einen rechten Winkel bei \(O\), bei \(P\) und bei \(Q\). Ist mindestens eines davon gleich null, wird der Zahler erhoht. Weil die Paarordnung nur in eine Richtung zugelassen wird, kann kein Dreieck doppelt gezahlt werden. Weil alle Rechnungen ganzzahlig sind, ist der Test exakt.
Die C++- und Java-Implementierungen heben die Produkte vor dem Addieren auf 64-Bit-Ganzzahlen an, sodass die Arithmetik auch fur andere \(n\)-Werte sicher bleibt. Die Python-Implementierung erhalt dieselbe Sicherheit automatisch durch das Integer-Modell der Sprache.
Sei \(M=(n+1)^2-1\) die Anzahl der Gitterpunkte auBer dem Ursprung. Das Verfahren pruift alle ungeordneten Paare, also ist die Laufzeit
$$\Theta\!\left(\binom{M}{2}\right)=\Theta(M^2)=\Theta(n^4).$$
Fur \(n=50\) sind das \(3{,}378{,}700\) Kandidatenpaare, und fur jedes Paar fallt nur konstante Arithmetik an. Darum ist die direkte Methode fur diese Aufgabe vollkommen praktikabel.
Der Zusatzspeicher hangt vom Implementierungsstil ab. Die direkten Vierfachschleifen brauchen auBer den Zahlern nur \(O(1)\) Speicher, wahrend die Variante mit vorgelagerter Punkteliste \(O(n^2)\) Speicher fur diese Liste benotigt. In beiden Fallen bleibt der Speicherverbrauch klein.
\(O=(0,0)\) olsun. \(P\) ve \(Q\), \(0 \le x,y \le 50\) karesi icindeki, orijin disindaki iki farkli kafes nokta olsun. Her sirasiz \(\{P,Q\}\) cifti bir \(OPQ\) aday ucgeni belirler. Istenen sey, bu adaylarin kac tanesinin dik ucgen oldugunu saymaktir.
C++, Python ve Java uygulamalari kapali bir formule dayanmiyor. Bunun yerine tam bir geometrik degismez kullaniyorlar: dik aci, skaler carpimin sifir olmasiyla tespit ediliyor. Izgara boyutu yeterince kucuk oldugu icin, orijin disindaki tum nokta ciftleri dogrudan test edilebiliyor.
\(P=(x_1,y_1)\) ve \(Q=(x_2,y_2)\) yazalim. Orijin sabit oldugundan, arama uzayi yalnizca farkli ve orijin olmayan kafes noktalarinin sirasiz ciftlerinden olusur. Dolayisiyla asil mesele ucgenleri tek tek cizmek degil; verilen bir \(\{P,Q\}\) cifti icin dik acinin \(O\), \(P\) ya da \(Q\) noktasinda olup olmadigini hizli ve kesin bicimde anlamaktir.
Kare icinde orijin haric \((50+1)^2-1=2600\) kafes nokta vardir. Bunlardan ikisini secince
$$\binom{2600}{2}=3{,}378{,}700$$
aday ucgen elde ederiz. Bu sayi elle analiz icin buyuk, fakat bilgisayarin dogrudan taramasi icin hala uygundur. Sirasiz cift kullanmak zorunludur; cunku \(OPQ\) ile \(OQP\) ayni ucgendir.
Dejenere olmayan bir ucgen en fazla bir dik aciya sahip olabilir. Bu nedenle uc olasi kose test edildiginde karar tamamen verilmis olur.
Dik aci yalnizca uc koseden birinde olabilir. Aday dik aci noktasindan cikilan vektorler su uc skaler-carpim testini verir:
$$\vec{OP}\cdot\vec{OQ}=x_1x_2+y_1y_2=0,$$
$$\vec{PO}\cdot\vec{PQ}=(-x_1,-y_1)\cdot(x_2-x_1,y_2-y_1)=x_1(x_1-x_2)+y_1(y_1-y_2)=0,$$
$$\vec{QO}\cdot\vec{QP}=(-x_2,-y_2)\cdot(x_1-x_2,y_1-y_2)=x_2(x_2-x_1)+y_2(y_2-y_1)=0.$$
Uygulamalarda hesaplanan tam olarak bu uc buyukluktur. Her sey tamsayi aritmetigiyle yapildigi icin kayan nokta belirsizligi yoktur ve geometrik yaklasim kullanilmaz.
Butun koordinatlar birinci bolgede oldugu icin negatif degildir. Bu yuzden
$$x_1x_2+y_1y_2=0$$
esitligi ancak bir nokta pozitif \(x\)-ekseni uzerinde, diger nokta da pozitif \(y\)-ekseni uzerindeyse saglanabilir. Dolayisiyla tam problemde orijinde dik acili ucgenlerin katkisi tam olarak \(50^2\), genel \(n\times n\) durumda ise \(n^2\) olur.
Bu gozlem brute-force algoritmasi icin zorunlu degildir, fakat guclu bir kontrol fikridir: orijin durumu yalnizca koordinatlarin isaret yapisindan tamamen belirlenir.
Dik aci \(P=(x_1,y_1)\) noktasindaysa, \(P\)'den \(Q\)'ya giden dogru parcasi ile \(P\)'den orijine giden dogru parcasi birbirine diktir. Vektor dilinde bu, \(\vec{PQ}\) ile \(\vec{OP}\)'nin ortogonal oldugu anlamina gelir. Simdi
$$g=\gcd(x_1,y_1)$$
olsun. \((x_1,y_1)\) vektorune dik olan ilkel kafes yonlerinden biri
$$\left(\frac{y_1}{g},-\frac{x_1}{g}\right)$$
ve digeri bunun ters isaretlisidir. O halde \(P\)'de dik aci ureten her kafes noktasi \(Q\), su iki isinlardan birinin uzerinde olmali:
$$Q=P\pm k\left(\frac{y_1}{g},-\frac{x_1}{g}\right)\qquad (k\in\mathbb{Z}_{>0}),$$
tabii koordinatlar \(0 \le x,y \le n\) karesi icinde kaldigi surece. Ayni aciklama, roller degistirilince \(Q\)'daki dik aci icin de gecerli olur. Kod bu perpendicular kafes dogrulari boyunca acikca yurumez; skaler-carpim kosullari zaten bu geometriyi cebirsel olarak ifade eder.
Ilk anlamli izgara \(n=2\) durumudur ve dogru cevap 14'tur. Skaler-carpim bakis acisi bu sonucu acik bir sekilde parcalar.
Orijinde dik acili \(n^2=4\) ucgen vardir: biri \(x\)-ekseni, biri \(y\)-ekseni uzerinde olmak uzere iki nokta secilir. Buna ek olarak, orijin disindaki eksen noktalarinda dik acili \(2n^2=8\) ucgen vardir. Ornegin \(O=(0,0)\), \(P=(1,0)\), \(Q=(1,1)\) secimi \(P\)'de dik aci verir.
Kalan iki ucgen ic noktasi \(P=(1,1)\)'den gelir. Burada \(g=\gcd(1,1)=1\) oldugu icin ilkel dik adim \((1,-1)\)'dir. \(2\times2\) kare icinde gecerli ortak noktalar \(Q=(2,0)\) ve \(Q=(0,2)\)'dir. \(Q=(2,0)\) icin
$$\vec{PO}\cdot\vec{PQ}=(-1,-1)\cdot(1,-1)=0$$
olur. Boylece toplam \(4+8+2=14\) elde edilir. Bu deger, uygulamalarin kullandigi dogruluk kontroluyle aynidir.
C++, Python ve Java uygulamalarinin sayim stratejisi aynidir. Once kare icindeki kafes noktalari uretilir ve orijin cikarilir. Daha sonra her sirasiz cift tam bir kez incelenir; bunu yapmak icin ya noktalar once bir listede tutulur ya da koordinat izgarasi dogrudan dolasilip tekrar eden ciftler atlanir.
Her aday cift icin uygulama, dik acinin \(O\), \(P\) ve \(Q\) noktalarinda olmasina karsilik gelen uc skaler carpimi hesaplar. Bunlardan en az biri sifirsa sayac bir artirilir. Cift sirasina yalnizca tek yonlu izin verildigi icin hicbir ucgen iki kez sayilmaz. Hesaplar tamsayi aritmetigiyle yapildigi icin test tamdir.
C++ ve Java uygulamalari carpimlari toplamadan once 64 bit tamsayiya yukseltir; boylece \(n\) degistirilse bile aritmetik guvenli kalir. Python uygulamasi ayni guvenligi dilin tamsayi modeli sayesinde kendiliginden elde eder.
\(M=(n+1)^2-1\), orijin disindaki kafes nokta sayisi olsun. Algoritma tum sirasiz ciftleri test ettigi icin zaman karmasikligi
$$\Theta\!\left(\binom{M}{2}\right)=\Theta(M^2)=\Theta(n^4)$$
olur. \(n=50\) icin bu, \(3{,}378{,}700\) aday cift demektir ve her cift icin yalnizca sabit sayida aritmetik islem gerekir. Bu nedenle dogrudan yontem bu problemde tamamen pratiktir.
Ek bellek kullanimi uygulama tarzina baglidir. Dogrudan ic ice donguler sayaclar disinda \(O(1)\) ek alan kullanir; once nokta listesini olusturan surum ise bu liste icin \(O(n^2)\) alan kullanir. Her iki durumda da bellek ayak izi kucuktur.
Sea \(O=(0,0)\). Sean \(P\) y \(Q\) dos puntos de la reticula dentro del cuadrado \(0 \le x,y \le 50\), distintos entre si y distintos del origen. Cada par no ordenado \(\{P,Q\}\) determina un triangulo candidato \(OPQ\). La tarea consiste en contar cuantos de esos triangulos son rectangulos.
Las implementaciones en C++, Python y Java no usan una formula cerrada. Se apoyan en un invariante geometrico exacto: un angulo recto se detecta cuando cierto producto escalar vale cero. Como la malla todavia es manejable, se puede probar directamente cada par no ordenado de puntos no nulos.
Escribamos \(P=(x_1,y_1)\) y \(Q=(x_2,y_2)\). Como el origen esta fijado, todo el espacio de busqueda queda reducido a pares no ordenados de puntos de la reticula distintos de \(O\). La cuestion central no es dibujar triangulos, sino reconocer con rapidez y sin ambiguedad si un par \(\{P,Q\}\) produce un angulo recto en \(O\), en \(P\) o en \(Q\).
Dentro del cuadrado hay \((50+1)^2-1=2600\) puntos de la reticula distintos del origen. Elegir dos de ellos produce
$$\binom{2600}{2}=3{,}378{,}700$$
triangulos candidatos. Es una cantidad demasiado grande para una clasificacion manual, pero sigue siendo perfectamente accesible para un barrido exhaustivo en computadora. Usar pares no ordenados es fundamental, porque \(OPQ\) y \(OQP\) representan el mismo triangulo.
Ademas, un triangulo no degenerado no puede tener dos angulos rectos. Una vez examinados los tres vertices posibles, la decision esta cerrada.
El angulo recto solo puede aparecer en uno de los tres vertices. Si se escriben los vectores con origen en el vertice candidato, se obtienen tres pruebas exactas mediante producto escalar:
$$\vec{OP}\cdot\vec{OQ}=x_1x_2+y_1y_2=0,$$
$$\vec{PO}\cdot\vec{PQ}=(-x_1,-y_1)\cdot(x_2-x_1,y_2-y_1)=x_1(x_1-x_2)+y_1(y_1-y_2)=0,$$
$$\vec{QO}\cdot\vec{QP}=(-x_2,-y_2)\cdot(x_1-x_2,y_1-y_2)=x_2(x_2-x_1)+y_2(y_2-y_1)=0.$$
Estas son exactamente las tres cantidades escalares que calculan las implementaciones. Todo se hace con aritmetica entera, de modo que no hay errores de punto flotante ni aproximaciones geometricas.
Como todas las coordenadas estan en el primer cuadrante, son no negativas. Por eso la igualdad
$$x_1x_2+y_1y_2=0$$
solo puede darse cuando un punto esta sobre el eje \(x\) positivo y el otro sobre el eje \(y\) positivo. Asi, los triangulos con angulo recto en \(O\) aportan exactamente \(50^2\) en el problema original, y en general \(n^2\) en una cuadrilla \(n\times n\).
La implementacion no necesita aislar este caso para contar, pero la observacion sirve como verificacion conceptual: el caso del origen queda completamente caracterizado por la estructura de signos de las coordenadas.
Si el angulo recto esta en \(P=(x_1,y_1)\), entonces el segmento \(PQ\) debe ser perpendicular al segmento \(PO\). En lenguaje vectorial, \(\vec{PQ}\) debe ser ortogonal a \(\vec{OP}\). Sea
$$g=\gcd(x_1,y_1).$$
Una direccion primitiva de la reticula perpendicular a \((x_1,y_1)\) es
$$\left(\frac{y_1}{g},-\frac{x_1}{g}\right),$$
y la otra es su opuesta. Por tanto, cualquier punto \(Q\) que produzca un angulo recto en \(P\) debe estar en uno de los dos rayos
$$Q=P\pm k\left(\frac{y_1}{g},-\frac{x_1}{g}\right)\qquad (k\in\mathbb{Z}_{>0}),$$
siempre que sus coordenadas permanezcan dentro del cuadrado \(0 \le x,y \le n\). La misma descripcion, intercambiando los papeles de \(P\) y \(Q\), explica el caso del angulo recto en \(Q\). El codigo no recorre explicitamente esas rectas perpendiculares; las condiciones de producto escalar son simplemente su version algebraica.
La malla no trivial mas pequena es \(n=2\), y alli la respuesta correcta es 14. La interpretacion mediante productos escalares permite ver claramente de donde sale ese numero.
Hay \(n^2=4\) triangulos con angulo recto en el origen: basta elegir un punto sobre el eje \(x\) y otro sobre el eje \(y\). Hay ademas \(2n^2=8\) triangulos con el angulo recto en un punto de un eje distinto del origen. Por ejemplo, \(O=(0,0)\), \(P=(1,0)\) y \(Q=(1,1)\) forman un angulo recto en \(P\).
Los dos restantes aparecen desde el punto interior \(P=(1,1)\). Aqui \(g=\gcd(1,1)=1\), de modo que un paso perpendicular primitivo es \((1,-1)\). Dentro del cuadrado \(2\times2\), los companeros validos son \(Q=(2,0)\) y \(Q=(0,2)\). Para \(Q=(2,0)\),
$$\vec{PO}\cdot\vec{PQ}=(-1,-1)\cdot(1,-1)=0.$$
Por tanto, el total es \(4+8+2=14\). Ese valor coincide con la comprobacion de correccion usada por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma estrategia de conteo. Primero enumeran los puntos de la reticula del cuadrado y eliminan el origen. Despues consideran cada par no ordenado exactamente una vez, ya sea guardando antes los puntos en una lista o recorriendo directamente la cuadrilla de coordenadas y descartando los pares que repetirian un triangulo ya visto.
Para cada par candidato, la implementacion calcula los tres productos escalares que corresponden a un angulo recto en \(O\), en \(P\) y en \(Q\). Si al menos uno vale cero, el contador aumenta en uno. Como el orden del par solo se permite en una direccion, ningun triangulo se cuenta dos veces. Y como toda la aritmetica es entera, la prueba es exacta.
Las versiones en C++ y Java elevan los productos a enteros de 64 bits antes de sumarlos, lo que mantiene segura la aritmetica incluso si se cambia \(n\). La version en Python obtiene esa misma seguridad automaticamente por el modelo de enteros del lenguaje.
Sea \(M=(n+1)^2-1\) el numero de puntos de la reticula distintos del origen. El algoritmo revisa todos los pares no ordenados, asi que el tiempo de ejecucion es
$$\Theta\!\left(\binom{M}{2}\right)=\Theta(M^2)=\Theta(n^4).$$
Para \(n=50\), eso significa \(3{,}378{,}700\) pares candidatos, y cada uno solo requiere una cantidad constante de operaciones aritmeticas. Por eso el metodo directo es totalmente practico en este problema.
El espacio auxiliar depende del estilo de implementacion. Las versiones con bucles anidados directos usan \(O(1)\) espacio extra aparte del contador, mientras que la variante que materializa primero la lista de puntos usa \(O(n^2)\) espacio para esa lista. En ambos casos el consumo de memoria es pequeno.
设 \(O=(0,0)\)。在正方形区域 \(0 \le x,y \le 50\) 内，取两个不同的格点 \(P\) 和 \(Q\)，并且二者都不能是原点。每一个无序点对 \(\{P,Q\}\) 都对应一个候选三角形 \(OPQ\)。题目要求统计其中有多少个是直角三角形。
C++、Python 和 Java 实现并没有依赖某个现成闭式公式，而是使用一个完全精确的几何判据：当且仅当某个点积为零时，候选三角形在相应顶点处出现直角。由于网格规模还不算大，直接检查所有无序格点对是可行的。
记 \(P=(x_1,y_1)\)，\(Q=(x_2,y_2)\)。因为原点 \(O\) 已经固定，所以整个搜索空间其实就是所有不同的、非原点格点组成的无序点对。于是问题的核心不是“如何画出所有三角形”，而是“给定 \(\{P,Q\}\) 后，怎样快速且无歧义地判断直角是在 \(O\)、\(P\) 还是 \(Q\)”。
在 \(0 \le x,y \le 50\) 的正方形中，一共有 \((50+1)^2-1=2600\) 个非原点格点。任取其中两个，可得到
$$\binom{2600}{2}=3{,}378{,}700$$
个候选三角形。这个数量显然不适合手工分类，但对计算机做一次完整扫描仍然完全现实。这里必须使用无序点对，因为 \(OPQ\) 与 \(OQP\) 描述的是同一个三角形。
另外，一个非退化三角形不可能同时拥有两个直角，所以只要把三个可能的直角位置全部检查一遍，结论就已经完整了。
直角只可能出现在三个顶点之一。把向量都写成“从候选直角顶点出发”的形式，就得到三个完全精确的点积条件：
$$\vec{OP}\cdot\vec{OQ}=x_1x_2+y_1y_2=0,$$
$$\vec{PO}\cdot\vec{PQ}=(-x_1,-y_1)\cdot(x_2-x_1,y_2-y_1)=x_1(x_1-x_2)+y_1(y_1-y_2)=0,$$
$$\vec{QO}\cdot\vec{QP}=(-x_2,-y_2)\cdot(x_1-x_2,y_1-y_2)=x_2(x_2-x_1)+y_2(y_2-y_1)=0.$$
实现中真正计算的，正是这三个标量。整个过程只涉及整数乘加，因此没有浮点误差，也不需要任何近似几何判断。
由于所有点都位于第一象限边界内，坐标都是非负数。因此
$$x_1x_2+y_1y_2=0$$
只有一种可能：一个点落在正 \(x\) 轴上，另一个点落在正 \(y\) 轴上。于是，在原题的 \(50\times50\) 网格中，直角位于原点的三角形恰好有 \(50^2\) 个；更一般地，在 \(n\times n\) 网格中贡献 \(n^2\) 个。
这个观察并不是算法必须显式利用的公式，但它是一个非常好的不变量检查：只要原点点积为零，几何结构就已经被坐标符号模式完全锁定了。
如果直角在 \(P=(x_1,y_1)\)，那么从 \(P\) 指向 \(Q\) 的边必须垂直于从 \(P\) 指向原点的边。也就是说，\(\vec{PQ}\) 必须与 \(\vec{OP}\) 正交。设
$$g=\gcd(x_1,y_1).$$
那么与向量 \((x_1,y_1)\) 垂直的一个原始格点方向可以写成
$$\left(\frac{y_1}{g},-\frac{x_1}{g}\right),$$
另一个方向则是它的相反数。因此，任何使 \(P\) 成为直角顶点的格点 \(Q\)，都必须落在下面两条射线之一上：
$$Q=P\pm k\left(\frac{y_1}{g},-\frac{x_1}{g}\right)\qquad (k\in\mathbb{Z}_{>0}),$$
前提是所得坐标仍然位于 \(0 \le x,y \le n\) 的边界内。把 \(P\) 与 \(Q\) 的角色互换，就得到直角在 \(Q\) 时的同样描述。代码并不会真的沿这些垂线方向逐点行走，但点积等于零的判据本质上就是这条格点垂线结构的代数写法。
最小的非平凡检查是 \(n=2\)，此时正确答案为 14。用上面的点积视角，可以把这 14 个三角形拆解得很清楚。
首先，直角在原点的三角形有 \(n^2=4\) 个：任选一个正 \(x\) 轴点，再任选一个正 \(y\) 轴点即可。其次，直角落在坐标轴上但不在原点的三角形有 \(2n^2=8\) 个。例如 \(O=(0,0)\)、\(P=(1,0)\)、\(Q=(1,1)\) 时，直角就在 \(P\)。
最后两个来自内部格点 \(P=(1,1)\)。这里 \(g=\gcd(1,1)=1\)，所以一个原始垂直步长是 \((1,-1)\)。在 \(2\times2\) 正方形内，可行的伙伴点只有 \(Q=(2,0)\) 和 \(Q=(0,2)\)。以 \(Q=(2,0)\) 为例，
$$\vec{PO}\cdot\vec{PQ}=(-1,-1)\cdot(1,-1)=0.$$
因此总数就是 \(4+8+2=14\)。这也正是实现所用的样例校验值。
C++、Python 和 Java 实现采用同一套计数思路。首先枚举正方形中的所有格点，并排除原点。然后只考察每一个无序点对一次，要么先把点收集成列表，再按下标取两点；要么直接在坐标网格上做嵌套循环，并跳过会重复先前三角形的点对。
对于每个候选点对，实现都会计算上面三个点积，分别对应直角在 \(O\)、在 \(P\)、以及在 \(Q\) 的情形。只要其中任意一个为零，就把答案加一。因为点对顺序只允许一种方向，所以不会重复计数。因为全部使用整数运算，所以判定没有精度风险。
C++ 和 Java 实现会先把乘法提升到 64 位整数，再进行求和，这样即使把 \(n\) 改大，运算也仍然安全。Python 实现则依靠语言本身的整数模型自动获得同样的安全性。
设 \(M=(n+1)^2-1\) 为非原点格点总数。算法需要检查所有无序点对，因此时间复杂度为
$$\Theta\!\left(\binom{M}{2}\right)=\Theta(M^2)=\Theta(n^4).$$
在 \(n=50\) 时，这意味着要检查 \(3{,}378{,}700\) 个候选点对，而每个点对只需要常数次整数运算。所以对本题而言，直接枚举并不只是“能做”，而且是非常自然、非常稳健的做法。
辅助空间取决于实现风格。直接使用嵌套循环的版本除了计数器几乎不需要额外空间，也就是 \(O(1)\)；先把格点物化成列表的版本则需要 \(O(n^2)\) 的额外空间来保存这些点。无论哪一种，内存占用都很小。
Пусть \(O=(0,0)\). Точки \(P\) и \(Q\) выбираются среди узлов решетки внутри квадрата \(0 \le x,y \le 50\), причем они различны и не совпадают с началом координат. Каждая неупорядоченная пара \(\{P,Q\}\) задает кандидат на треугольник \(OPQ\). Нужно посчитать, сколько таких треугольников являются прямоугольными.
Реализации на C++, Python и Java не опираются на готовую закрытую формулу. Вместо этого они используют точный геометрический инвариант: прямой угол распознается по нулевому скалярному произведению. Размер сетки еще достаточно мал, чтобы можно было напрямую проверить каждую неупорядоченную пару ненулевых точек.
Обозначим \(P=(x_1,y_1)\) и \(Q=(x_2,y_2)\). Так как вершина \(O\) фиксирована, все пространство поиска сводится к неупорядоченным парам различных решетчатых точек, отличных от начала координат. Значит, главный вопрос не в том, как перечислить сами треугольники, а в том, как для данной пары \(\{P,Q\}\) быстро и точно определить, находится ли прямой угол в \(O\), в \(P\) или в \(Q\).
В квадрате имеется \((50+1)^2-1=2600\) решетчатых точек, кроме начала координат. Выбор любых двух дает
$$\binom{2600}{2}=3{,}378{,}700$$
кандидатных треугольников. Это слишком много для ручного разбора, но вполне посильно для полного перебора на компьютере. Использование неупорядоченных пар принципиально важно, потому что \(OPQ\) и \(OQP\) описывают один и тот же треугольник.
Невырожденный треугольник не может иметь два прямых угла. Поэтому после проверки трех возможных вершин решение уже полностью определено.
Прямой угол может стоять только в одной из трех вершин. Если брать векторы с началом в предполагаемой прямой вершине, получаются три точных теста через скалярное произведение:
$$\vec{OP}\cdot\vec{OQ}=x_1x_2+y_1y_2=0,$$
$$\vec{PO}\cdot\vec{PQ}=(-x_1,-y_1)\cdot(x_2-x_1,y_2-y_1)=x_1(x_1-x_2)+y_1(y_1-y_2)=0,$$
$$\vec{QO}\cdot\vec{QP}=(-x_2,-y_2)\cdot(x_1-x_2,y_1-y_2)=x_2(x_2-x_1)+y_2(y_2-y_1)=0.$$
Именно эти три скалярные величины и вычисляются в реализациях. Все делается в целочисленной арифметике, поэтому нет ни ошибок округления, ни приближенной геометрии.
Все координаты лежат в первом квадранте, то есть неотрицательны. Поэтому равенство
$$x_1x_2+y_1y_2=0$$
возможно только тогда, когда одна точка лежит на положительной оси \(x\), а другая на положительной оси \(y\). Значит, вклад треугольников с прямым углом в \(O\) равен ровно \(50^2\) в исходной задаче и вообще \(n^2\) на сетке \(n\times n\).
Для самого brute-force алгоритма это разбиение не обязательно, но как инвариант оно очень полезно: случай прямого угла в начале координат полностью определяется знаковой структурой координат.
Если прямой угол находится в \(P=(x_1,y_1)\), то отрезок \(PQ\) должен быть перпендикулярен отрезку \(PO\). В векторной форме это означает, что \(\vec{PQ}\) ортогонален \(\vec{OP}\). Пусть
$$g=\gcd(x_1,y_1).$$
Тогда примитивное решетчатое направление, перпендикулярное вектору \((x_1,y_1)\), имеет вид
$$\left(\frac{y_1}{g},-\frac{x_1}{g}\right),$$
а второе направление получается сменой знака. Следовательно, любая решетчатая точка \(Q\), дающая прямой угол в \(P\), должна лежать на одном из лучей
$$Q=P\pm k\left(\frac{y_1}{g},-\frac{x_1}{g}\right)\qquad (k\in\mathbb{Z}_{>0}),$$
при условии, что координаты остаются внутри квадрата \(0 \le x,y \le n\). Ровно та же картина, только с обменом ролей, описывает случай прямого угла в \(Q\). Код не шагает по этим перпендикулярным решетчатым прямым напрямую; скалярные условия просто являются их алгебраической формой.
Первый нетривиальный случай - это \(n=2\), и правильный ответ там равен 14. Представление через скалярные произведения позволяет увидеть эту цифру по частям.
Есть \(n^2=4\) треугольника с прямым углом в начале координат: нужно выбрать одну точку на оси \(x\) и одну на оси \(y\). Еще \(2n^2=8\) треугольников имеют прямой угол в точке на одной из осей, но не в начале координат. Например, \(O=(0,0)\), \(P=(1,0)\), \(Q=(1,1)\) дают прямой угол в \(P\).
Оставшиеся два возникают из внутренней точки \(P=(1,1)\). Здесь \(g=\gcd(1,1)=1\), поэтому примитивный перпендикулярный шаг равен \((1,-1)\). Внутри квадрата \(2\times2\) допустимыми партнерами являются \(Q=(2,0)\) и \(Q=(0,2)\). Для \(Q=(2,0)\) имеем
$$\vec{PO}\cdot\vec{PQ}=(-1,-1)\cdot(1,-1)=0.$$
Итак, суммарно получаем \(4+8+2=14\). Это ровно то контрольное значение, на которое ориентируются реализации.
Реализации на C++, Python и Java используют одну и ту же схему подсчета. Сначала они перечисляют решетчатые точки квадрата и исключают начало координат. Затем каждая неупорядоченная пара рассматривается ровно один раз: либо точки заранее сохраняются в массиве, либо координатная сетка обходится напрямую, а повторяющие уже встреченный треугольник пары пропускаются.
Для каждой пары программа вычисляет три скалярных произведения, отвечающих прямому углу в \(O\), в \(P\) и в \(Q\). Если хотя бы одно из них равно нулю, счетчик увеличивается. Односторонний порядок перебора гарантирует отсутствие двойного счета, а целочисленная арифметика делает проверку совершенно точной.
В версиях на C++ и Java произведения сначала переводятся в 64-битный тип, чтобы арифметика оставалась безопасной даже при изменении \(n\). В Python такая безопасность обеспечивается самой моделью целых чисел.
Пусть \(M=(n+1)^2-1\) - число решетчатых точек, отличных от начала координат. Алгоритм проверяет все неупорядоченные пары, поэтому время работы равно
$$\Theta\!\left(\binom{M}{2}\right)=\Theta(M^2)=\Theta(n^4).$$
При \(n=50\) это означает \(3{,}378{,}700\) кандидатных пар, и на каждую пару приходится лишь константное количество арифметики. Поэтому прямой перебор для этой задачи полностью практичен.
Дополнительная память зависит от стиля реализации. Версии с прямыми вложенными циклами используют \(O(1)\) extra-памяти сверх счетчиков, а вариант с предварительным списком точек требует \(O(n^2)\) памяти для этого списка. В обоих случаях объем памяти невелик.
لتكن \(O=(0,0)\). نختار نقطتين شبكيتين \(P\) و\(Q\) داخل المربع \(0 \le x,y \le 50\)، على أن تكونا مختلفتين عن بعضهما ومختلفتين عن نقطة الأصل. كل زوج غير مرتب \(\{P,Q\}\) يحدد مثلثًا مرشحًا \(OPQ\). المطلوب هو عدّ عدد هذه المثلثات التي تكون قائمة الزاوية.
التنفيذات في ++C وPython وJava لا تعتمد على صيغة مغلقة جاهزة، بل تعتمد على ثابت هندسي دقيق: وجود زاوية قائمة يعادل أن يكون أحد حواصل الضرب النقطي مساويًا للصفر. وبما أن حجم الشبكة ما زال محدودًا، فيمكن فحص كل زوج غير مرتب من النقاط غير الصفرية مباشرة.
لنكتب \(P=(x_1,y_1)\) و\(Q=(x_2,y_2)\). بما أن الأصل ثابت، فإن فضاء البحث كله يختزل إلى الأزواج غير المرتبة من النقاط الشبكية المختلفة وغير الواقعة عند الأصل. لذلك فجوهر المسألة ليس رسم المثلثات، بل تحديد معيار حاسم وسريع يجيب: هل الزاوية القائمة تقع عند \(O\) أم عند \(P\) أم عند \(Q\)؟
عدد النقاط الشبكية غير الأصلية داخل المربع هو \((50+1)^2-1=2600\). واختيار نقطتين منها يعطي
$$\binom{2600}{2}=3{,}378{,}700$$
مثلثًا مرشحًا. هذا العدد كبير على التحليل اليدوي، لكنه ما زال مناسبًا تمامًا لمسح شامل بالحاسوب. واستخدام الأزواج غير المرتبة ضروري، لأن \(OPQ\) و\(OQP\) هما في الحقيقة المثلث نفسه.
كما أن المثلث غير المنعدم لا يمكن أن يملك زاويتين قائمتين، لذا فإن اختبار الرؤوس الثلاثة الممكنة يكفي تمامًا للحسم.
يمكن أن تظهر الزاوية القائمة عند واحد فقط من الرؤوس الثلاثة. وإذا كتبنا المتجهات انطلاقًا من الرأس المرشح، نحصل على ثلاثة اختبارات دقيقة بالضرب النقطي:
$$\vec{OP}\cdot\vec{OQ}=x_1x_2+y_1y_2=0,$$
$$\vec{PO}\cdot\vec{PQ}=(-x_1,-y_1)\cdot(x_2-x_1,y_2-y_1)=x_1(x_1-x_2)+y_1(y_1-y_2)=0,$$
$$\vec{QO}\cdot\vec{QP}=(-x_2,-y_2)\cdot(x_1-x_2,y_1-y_2)=x_2(x_2-x_1)+y_2(y_2-y_1)=0.$$
هذه هي بالضبط الكميات الثلاث التي تحسبها التنفيذات. كل شيء يتم بحسابات صحيحة، لذلك لا توجد أخطاء فاصلة عائمة ولا تقريب هندسي.
جميع الإحداثيات غير سالبة لأن النقاط تقع في الربع الأول وحدوده. لذلك فإن المعادلة
$$x_1x_2+y_1y_2=0$$
لا يمكن أن تتحقق إلا إذا كانت إحدى النقطتين على المحور \(x\) الموجب والأخرى على المحور \(y\) الموجب. ومن ثم فإن عدد المثلثات ذات الزاوية القائمة عند \(O\) يساوي تمامًا \(50^2\) في المسألة الأصلية، وبصورة عامة يساوي \(n^2\) على شبكة \(n\times n\).
هذا الاستنتاج ليس ضروريًا لتنفيذ العد الشامل، لكنه يعد فحصًا هندسيًا ممتازًا: حالة الأصل يمكن تمييزها بالكامل من بنية إشارات الإحداثيات.
إذا كانت الزاوية القائمة عند \(P=(x_1,y_1)\)، فيجب أن يكون الضلع \(PQ\) عموديًا على الضلع \(PO\). أي أن \(\vec{PQ}\) يجب أن يكون متعامدًا مع \(\vec{OP}\). ولتكن
$$g=\gcd(x_1,y_1).$$
عندئذ يكون أحد الاتجاهات الشبكية الأولية العمودية على \((x_1,y_1)\) هو
$$\left(\frac{y_1}{g},-\frac{x_1}{g}\right),$$
والاتجاه الآخر هو سالب هذا المتجه. لذلك فإن أي نقطة شبكية \(Q\) تجعل الزاوية قائمة عند \(P\) يجب أن تقع على أحد الشعاعين
$$Q=P\pm k\left(\frac{y_1}{g},-\frac{x_1}{g}\right)\qquad (k\in\mathbb{Z}_{>0}),$$
ما دامت الإحداثيات تبقى داخل المربع \(0 \le x,y \le n\). والوصف نفسه، مع تبديل الدورين، يشرح حالة الزاوية القائمة عند \(Q\). التنفيذ لا يسير على هذه الأشعة العمودية خطوة بخطوة، لكن شرط الضرب النقطي الصفري هو الصياغة الجبرية المباشرة لهذا الوصف الهندسي.
أصغر شبكة غير تافهة هي \(n=2\)، والنتيجة الصحيحة فيها هي 14. ومنظور الضرب النقطي يوضح هذا العدد بطريقة منظمة.
هناك \(n^2=4\) مثلثات تكون الزاوية القائمة فيها عند الأصل: نختار نقطة على المحور \(x\) ونقطة على المحور \(y\). وهناك أيضًا \(2n^2=8\) مثلثات تكون الزاوية القائمة فيها عند نقطة تقع على أحد المحورين بعيدًا عن الأصل. مثلًا، النقاط \(O=(0,0)\) و\(P=(1,0)\) و\(Q=(1,1)\) تعطي زاوية قائمة عند \(P\).
أما المثلثان الباقيان فيأتيان من النقطة الداخلية \(P=(1,1)\). هنا لدينا \(g=\gcd(1,1)=1\)، لذا فإن خطوة عمودية أولية هي \((1,-1)\). داخل المربع \(2\times2\)، النقطتان المناسبتان هما \(Q=(2,0)\) و\(Q=(0,2)\). وبالنسبة إلى \(Q=(2,0)\)، نحصل على
$$\vec{PO}\cdot\vec{PQ}=(-1,-1)\cdot(1,-1)=0.$$
إذًا يكون المجموع \(4+8+2=14\). وهذه هي نفسها قيمة التحقق التي تعتمد عليها التنفيذات.
التنفيذات في ++C وPython وJava تتبع الاستراتيجية نفسها في العد. فهي تبدأ بتوليد جميع النقاط الشبكية داخل المربع مع استبعاد الأصل، ثم تفحص كل زوج غير مرتب مرة واحدة فقط، إما عبر تخزين النقاط أولًا في قائمة، أو عبر الدوران المباشر على شبكة الإحداثيات مع تجاوز الأزواج التي تعيد مثلثًا سبق احتسابه.
لكل زوج مرشح، يحسب التنفيذ حواصل الضرب النقطي الثلاثة المقابلة لاحتمال أن تكون الزاوية القائمة عند \(O\) أو عند \(P\) أو عند \(Q\). فإذا كان واحد منها على الأقل يساوي الصفر، زاد العداد بمقدار واحد. وبما أن ترتيب الزوج لا يسمح إلا في اتجاه واحد، فلا يحدث عد مزدوج. وبما أن الحساب كله صحيح تمامًا، فالاختبار خالٍ من أي التباس عددي.
نسختا ++C وJava ترفعان الضربات إلى أعداد صحيحة بعرض 64 بت قبل جمعها، مما يبقي الحساب آمنًا حتى لو تغيرت قيمة \(n\). أما Python فتحصل على الأمان نفسه تلقائيًا من نموذج الأعداد الصحيحة في اللغة.
إذا رمزنا بعدد النقاط الشبكية غير الأصلية بـ \(M=(n+1)^2-1\)، فإن الخوارزمية تفحص جميع الأزواج غير المرتبة، ولهذا يكون زمن التنفيذ
$$\Theta\!\left(\binom{M}{2}\right)=\Theta(M^2)=\Theta(n^4).$$
عند \(n=50\)، يعني ذلك فحص \(3{,}378{,}700\) زوجًا مرشحًا، وكل زوج يحتاج إلى عدد ثابت فقط من العمليات الحسابية. لهذا السبب فإن المنهج المباشر عملي تمامًا في هذه المسألة.
المساحة الإضافية تعتمد على أسلوب التنفيذ. النسخ التي تستخدم حلقات متداخلة مباشرة تحتاج إلى \(O(1)\) مساحة إضافية فوق العدادات، بينما النسخة التي تبني قائمة بالنقاط أولًا تحتاج إلى \(O(n^2)\) مساحة لتلك القائمة. وفي الحالتين يبقى استهلاك الذاكرة صغيرًا.