Let
$$P_r=\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}:x^2+y^2\lt r^2\}.$$
For the actual Project Euler input, \(r=105\). The task is to count unordered triangles whose three vertices are chosen from \(P_{105}\) and whose interior contains the origin strictly, not merely on an edge or on a degenerate line.
A direct approach would examine all \(\binom{N}{3}\) triples of lattice points and run a point-in-triangle test on each one, where \(N=|P_r|\). The implementations avoid that completely. They reorganize the point set by polar angle, group points that lie on the same ray from the origin, and then subtract the triples that are geometrically impossible instead of testing triangles one by one.
A nondegenerate triangle contains the origin if and only if the origin lies in the convex hull of its three vertices. Equivalently, a triangle misses the origin if there exists a line through the origin such that all three vertices lie in one closed half-plane determined by that line. In angular language, that means the three vertex directions fit inside some closed interval of length \(\pi\).
So the problem is easier to solve in complementary form: count all triples of lattice points, then subtract every triple whose three directions can be packed into a closed semicircle, together with the collinear cases where the “triangle” has zero area.
When two lattice points have the same polar angle, they lie on the same ray from the origin. If \((u,v)\) is a primitive lattice direction with \(\gcd(u,v)=1\), then the points on that ray are
$$ (u,v),\ 2(u,v),\ 3(u,v),\dots $$
up to the largest multiple still satisfying \(k^2(u^2+v^2)\lt r^2\). Let \(c\) denote the number of such points on one ray. The opposite ray \((-u,-v)\) has the same multiplicity \(c\), so each unoriented line through the origin contributes \(2c\) lattice points altogether.
Now let \(N=|P_r|\). By central symmetry, every point is paired with its opposite, so \(N\) is even. Write
$$H=\frac{N}{2}.$$
For a fixed line through the origin with multiplicity \(c\) on each ray, removing the \(2c\) points on the line leaves \(N-2c\) points off the line, split evenly between the two open half-planes. Therefore each open side contains exactly \(H-c\) points.
Fix one such line and classify every triple that fails the strict containment condition because of this line. The bad triples are mutually exclusive and fall into four natural types.
1. One boundary vertex, two interior vertices on the same side. Choose one vertex on either ray of the line, then choose two vertices from the open half-plane on that same side. This gives
$$2c\binom{H-c}{2}=c(H-c)(H-c-1).$$
The factor \(2\) reflects the fact that either of the two opposite rays can supply the boundary vertex of the minimal closed semicircle.
2. Two vertices on the same ray, third vertex on that same side. If two chosen points lie on one ray and the third lies strictly in the adjacent open half-plane, the origin cannot lie inside the triangle. Counting both rays gives
$$2\binom{c}{2}(H-c)=c(c-1)(H-c).$$
3. One vertex on each opposite ray. Then the segment joining those two vertices passes through the origin, so the origin lies on an edge rather than in the interior. The third vertex can be any point not on the same line, hence
$$c^2(N-2c).$$
4. All three vertices on the same line through the origin. These choices are degenerate and contribute
$$\binom{2c}{3}.$$
Summing these four contributions over all unoriented lines through the origin counts every triple that does not produce a valid “origin-containing” triangle exactly once.
For \(r=2\), the nonzero interior lattice points are the four axis points and the four diagonal points, so \(N=8\) and \(H=4\). There are four relevant lines through the origin, and each one has \(c=1\) point on each ray.
For one line the bad contribution is
$$1\cdot(4-1)(4-2)+1^2(8-2)+1\cdot 0\cdot(4-1)+\binom{2}{3}=6+6+0+0=12.$$
All four lines behave the same way, so the total number of bad triples is \(4\cdot 12=48\). Since
$$\binom{8}{3}=56,$$
the number of triangles containing the origin is
$$56-48=8,$$
which matches the checkpoint used by the implementations.
If the equal-angle groups from one half-turn have multiplicities \(c_1,c_2,\dots,c_m\), then each \(c_j\) represents one unoriented line through the origin, and the final answer is
$$\boxed{\binom{N}{3}-\sum_{j=1}^{m}\left(c_j(H-c_j)(H-c_j-1)+c_j^2(N-2c_j)+c_j(c_j-1)(H-c_j)+\binom{2c_j}{3}\right).}$$
This is the exact mathematics implemented by the C++, Python, and Java solutions. The source code simply writes the middle two contributions as one combined subtraction.
The C++, Python, and Java implementations enumerate every integer point in the square \([-r,r]\times[-r,r]\), discard the origin and every point on or outside the circle, and compute the polar angle \(\operatorname{atan2}(y,x)\) for each surviving point. After sorting those angles, equal-angle runs correspond precisely to points that share one ray from the origin.
Because every lattice point has the opposite point \((-x,-y)\), the sorted angle list naturally breaks into opposite pairs separated by \(\pi\). That is why the implementations only scan one half of the sorted list: this visits each line through the origin exactly once. During that scan, a small tolerance is used to merge angles that should be identical mathematically.
The running total starts at \(\binom{N}{3}\). For each equal-angle run of size \(c\), the implementation evaluates the three subtraction statements visible in the code: the “one boundary vertex” term, the combined “two on a ray or one on each opposite ray” term, and the fully collinear term \(\binom{2c}{3}\). After every representative line has been processed, the remaining total is exactly the number of triangles that contain the origin strictly inside.
The grid scan checks \((2r+1)^2\) candidate lattice points, so the enumeration phase costs \(O(r^2)\). If \(N=|P_r|\), then \(N=\Theta(r^2)\), and sorting the angle list costs \(O(N\log N)\).
The final grouping pass is linear, \(O(N)\), and memory usage is \(O(N)\) for the stored angles. For the actual value \(r=105\), this is comfortably fast because the method never performs an explicit \(O(N^3)\) triangle test.
Definiere
$$P_r=\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}:x^2+y^2\lt r^2\}.$$
Für die eigentliche Aufgabe gilt \(r=105\). Gesucht ist die Anzahl ungeordneter Dreiecke, deren drei Ecken aus \(P_{105}\) stammen und deren Inneres den Ursprung strikt enthält, also weder nur auf einer Kante noch auf einer entarteten Geraden liegt.
Ein naiver Ansatz würde alle \(\binom{N}{3}\) Punkttripel durchgehen und für jedes Dreieck einzeln testen, ob der Ursprung darin liegt. Die Implementierungen vermeiden das vollständig. Sie ordnen die Punkte stattdessen nach Polarwinkeln, fassen Punkte auf demselben Strahl zusammen und subtrahieren dann genau die Tripel, die geometrisch niemals als gültige Lösung in Frage kommen.
Ein nicht entartetes Dreieck enthält den Ursprung genau dann, wenn der Ursprung in der konvexen Hülle seiner drei Ecken liegt. Äquivalent dazu gilt: Ein Dreieck verfehlt den Ursprung genau dann, wenn es eine Gerade durch den Ursprung gibt, so dass alle drei Ecken in einer von dieser Geraden bestimmten abgeschlossenen Halbebene liegen. In Winkelsprache bedeutet das, dass die drei Richtungen in ein abgeschlossenes Intervall der Länge \(\pi\) passen.
Darum ist es viel günstiger, das Komplement zu zählen: zuerst alle Punkttripel, dann alle Tripel abziehen, deren Richtungen in einer abgeschlossenen Halbkreisscheibe liegen, sowie die kollinearen Fälle, bei denen die „Dreiecke“ überhaupt keinen Flächeninhalt haben.
Haben zwei Gitterpunkte denselben Polarwinkel, dann liegen sie auf demselben Strahl vom Ursprung. Ist \((u,v)\) eine primitive Gitterrichtung mit \(\gcd(u,v)=1\), dann liegen auf diesem Strahl genau die Punkte
$$ (u,v),\ 2(u,v),\ 3(u,v),\dots $$
bis zum größten Vielfachen, das noch \(k^2(u^2+v^2)\lt r^2\) erfüllt. Sei \(c\) die Anzahl dieser Punkte auf einem Strahl. Auf dem Gegenstrahl \((-u,-v)\) liegen ebenfalls \(c\) Punkte, also liefert jede ungerichtete Gerade durch den Ursprung insgesamt \(2c\) Gitterpunkte.
Setze nun \(N=|P_r|\). Wegen der Zentralsymmetrie gehört zu jedem Punkt auch sein Gegenpunkt, also ist \(N\) gerade. Schreibe
$$H=\frac{N}{2}.$$
Fixiert man eine Gerade mit Multiplikität \(c\) auf jedem der beiden Strahlen, dann bleiben nach Entfernen der \(2c\) Randpunkte genau \(N-2c\) Punkte übrig. Diese verteilen sich gleichmäßig auf die beiden offenen Halbebenen, also liegen auf jeder Seite genau \(H-c\) Punkte.
Fixiere nun eine solche Gerade und klassifiziere alle Tripel, die wegen dieser Geraden den Ursprung nicht strikt enthalten. Diese schlechten Konfigurationen sind paarweise disjunkt und zerfallen in vier natürliche Typen.
1. Ein Randpunkt, zwei innere Punkte auf derselben Seite. Wähle einen Eckpunkt auf einem der beiden Strahlen und danach zwei Punkte aus der offenen Halbebene auf derselben Seite. Das ergibt
$$2c\binom{H-c}{2}=c(H-c)(H-c-1).$$
Der Faktor \(2\) berücksichtigt, dass der Randstrahl des minimalen abgeschlossenen Halbkreises auf einer der beiden entgegengesetzten Seiten liegen kann.
2. Zwei Punkte auf demselben Strahl, der dritte auf derselben Seite. Liegen zwei gewählte Punkte auf demselben Strahl und der dritte strikt in der benachbarten offenen Halbebene, dann kann der Ursprung nicht im Inneren liegen. Für beide Strahlen zusammen erhält man
$$2\binom{c}{2}(H-c)=c(c-1)(H-c).$$
3. Je ein Punkt auf zwei Gegenstrahlen. Dann verläuft die Verbindungsstrecke dieser beiden Punkte durch den Ursprung, also liegt der Ursprung auf einer Kante und nicht im Inneren. Der dritte Punkt kann beliebig außerhalb der Geraden gewählt werden, also
$$c^2(N-2c).$$
4. Alle drei Punkte liegen auf derselben Geraden durch den Ursprung. Diese Wahl ist entartet und trägt
$$\binom{2c}{3}$$
bei. Summiert man diese vier Beiträge über alle ungerichteten Geraden durch den Ursprung, dann wird jedes ungültige Tripel genau einmal erfasst.
Für \(r=2\) bestehen die nichtnulligen inneren Gitterpunkte aus den vier Achsenpunkten und den vier Diagonalpunkten. Also gilt \(N=8\) und \(H=4\). Es gibt vier relevante Geraden durch den Ursprung, und auf jedem der beiden Strahlen einer solchen Geraden liegt genau \(c=1\) Punkt.
Für eine einzelne Gerade ist der schlechte Beitrag
$$1\cdot(4-1)(4-2)+1^2(8-2)+1\cdot 0\cdot(4-1)+\binom{2}{3}=6+6+0+0=12.$$
Alle vier Geraden verhalten sich gleich, also gibt es insgesamt \(4\cdot 12=48\) schlechte Tripel. Da
$$\binom{8}{3}=56,$$
bleiben
$$56-48=8$$
gültige Dreiecke übrig. Genau dieser Wert erscheint auch als Kontrollpunkt in den Implementierungen.
Haben die Gleichwinkel-Gruppen in einer Halbkreisdrehung die Multiplizitäten \(c_1,c_2,\dots,c_m\), dann steht jedes \(c_j\) für genau eine ungerichtete Gerade durch den Ursprung. Die gesuchte Anzahl ist dann
$$\boxed{\binom{N}{3}-\sum_{j=1}^{m}\left(c_j(H-c_j)(H-c_j-1)+c_j^2(N-2c_j)+c_j(c_j-1)(H-c_j)+\binom{2c_j}{3}\right).}$$
Genau diese Mathematik setzen die C++-, Python- und Java-Lösungen um. Im Code sind nur die beiden mittleren Beiträge zu einer einzigen Subtraktion zusammengefasst.
Die Implementierungen in C++, Python und Java laufen zuerst über alle ganzzahligen Punkte im Quadrat \([-r,r]\times[-r,r]\), verwerfen den Ursprung sowie alle Punkte auf oder außerhalb des Kreises und berechnen für jeden verbleibenden Punkt den Polarwinkel \(\operatorname{atan2}(y,x)\). Nach dem Sortieren entsprechen zusammenhängende Gruppen gleicher Winkel genau den Punkten auf demselben Ursprungstrahl.
Da zu jedem Gitterpunkt auch der Gegenpunkt \((-x,-y)\) existiert, zerfällt die sortierte Winkelliste natürlich in entgegengesetzte Paare im Abstand \(\pi\). Deshalb reicht es, nur die erste Hälfte der sortierten Liste zu scannen: So wird jede Gerade durch den Ursprung genau einmal besucht. Beim Zusammenfassen gleicher Winkel verwenden die Implementierungen eine kleine Toleranz, um numerische Rundung bei Gleitkommazahlen robust zu behandeln.
Der laufende Wert startet bei \(\binom{N}{3}\). Für jede Gruppe der Größe \(c\) werden dann genau die drei im Quelltext sichtbaren Subtraktionen ausgewertet: der Beitrag mit einem Randpunkt, der kombinierte Beitrag „zwei auf einem Strahl oder je einer auf zwei Gegenstrahlen“ und der kollineare Beitrag \(\binom{2c}{3}\). Nach der Verarbeitung aller repräsentativen Geraden bleibt exakt die Anzahl der Dreiecke übrig, die den Ursprung strikt enthalten.
Der Gitterscan prüft \((2r+1)^2\) Kandidatenpunkte, also kostet die Enumerationsphase \(O(r^2)\). Mit \(N=|P_r|\) gilt außerdem \(N=\Theta(r^2)\), daher kostet das Sortieren der Winkel \(O(N\log N)\).
Der abschließende Gruppendurchlauf ist linear, also \(O(N)\), und der Speicherbedarf beträgt \(O(N)\) für die Winkelliste. Für den konkreten Eingabewert \(r=105\) ist das problemlos schnell, weil nirgends ein expliziter \(O(N^3)\)-Dreieckstest ausgeführt wird.
Şu kümeyi tanımlayalım:
$$P_r=\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}:x^2+y^2\lt r^2\}.$$
Gerçek Project Euler girdisinde \(r=105\) alınır. İstenen şey, köşeleri \(P_{105}\) kümesinden seçilen ve orijini yalnızca bir kenar üzerinde değil, gerçekten iç bölgesinde barındıran sırasız üçgenlerin sayısıdır.
Doğrudan çözüm, \(\binom{N}{3}\) nokta üçlüsünün hepsini üretip her biri için ayrı bir “nokta üçgenin içinde mi?” testi yapmak olurdu. Uygulamalar bunu hiç yapmıyor. Bunun yerine noktaları kutupsal açıya göre düzenliyor, aynı ışın üzerinde bulunan noktaları gruplayıp geçersiz üçlüleri kapalı bir formülle çıkarıyor.
Entartı olmayan bir üçgen, ancak ve ancak orijin üç köşenin konveks zarfı içindeyse orijini içerir. Bunun eşdeğer karşıtı şudur: Eğer üçgen orijini içermiyorsa, orijinden geçen öyle bir doğru vardır ki üç köşenin tamamı bu doğrunun belirlediği kapalı bir yarı düzlemde kalır. Açılar cinsinden bakınca bu, üç yönün uzunluğu \(\pi\) olan kapalı bir aralığa sığması demektir.
Dolayısıyla problemi tamamlayıcı sayımla çözmek daha kolaydır: önce bütün nokta üçlülerini say, sonra yönleri bir kapalı yarım çembere sığanları ve alanı sıfır olan doğrusal durumları çıkar.
İki kafes noktasının kutupsal açısı aynıysa, bu iki nokta orijinden çıkan aynı ışın üzerindedir. \((u,v)\) asal bir kafes yönü ve \(\gcd(u,v)=1\) ise, bu ışın üzerindeki noktalar
$$ (u,v),\ 2(u,v),\ 3(u,v),\dots $$
şeklindedir ve en büyük çokluğun hâlâ \(k^2(u^2+v^2)\lt r^2\) şartını sağlaması gerekir. Bir ışın üzerindeki böyle nokta sayısına \(c\) diyelim. Karşıt ışın \((-u,-v)\) üzerinde de yine \(c\) nokta vardır; yani orijinden geçen her yönsüz doğru toplam \(2c\) nokta üretir.
Şimdi \(N=|P_r|\) olsun. Merkez simetrisinden ötürü her noktanın bir zıt noktası vardır; bu yüzden \(N\) çifttir. Şunu yazalım:
$$H=\frac{N}{2}.$$
Belirli bir doğru için her iki ışında da \(c\) nokta varsa, doğru üzerindeki \(2c\) noktayı çıkarınca geriye \(N-2c\) nokta kalır. Bunlar iki açık yarı düzleme eşit dağılır, dolayısıyla her açık tarafta tam olarak \(H-c\) nokta bulunur.
Şimdi böyle bir doğruyu sabitleyelim ve bu doğru yüzünden orijini sıkı biçimde içeremeyen bütün üçlüleri sınıflandıralım. Bu geçersiz üçlüler ayrık dört doğal tipe ayrılır.
1. Sınırda bir köşe, aynı tarafta iki iç köşe. Doğrunun iki ışınından birindeki bir köşeyi seçip sonra aynı taraftaki açık yarı düzlemden iki köşe daha seçersek
$$2c\binom{H-c}{2}=c(H-c)(H-c-1)$$
elde ederiz. Buradaki \(2\) katsayısı, minimal kapalı yarım çemberin sınır ışınının iki karşıt ışından hangisi olacağını seçer.
2. Aynı ışın üzerinde iki köşe, aynı tarafta üçüncü köşe. Seçilen iki nokta aynı ışın üzerindeyse ve üçüncü nokta da aynı taraftaki açık yarı düzlemdeyse, orijin iç bölgede olamaz. İki ışın birlikte
$$2\binom{c}{2}(H-c)=c(c-1)(H-c)$$
katkı verir.
3. Karşıt iki ışında birer köşe. Bu durumda bu iki köşeyi birleştiren doğru parçası orijinden geçer; yani orijin içte değil, bir kenarın üzerindedir. Üçüncü köşe aynı doğru dışında herhangi bir nokta olabilir, dolayısıyla sayı
$$c^2(N-2c)$$
olur.
4. Üç köşenin de aynı doğru üzerinde olması. Bunlar yoz üçgenlerdir ve
$$\binom{2c}{3}$$
adet katkı yapar. Bu dört terimi orijinden geçen bütün yönsüz doğrular üzerinde topladığımızda, orijini içermeyen her üçlü tam bir kez sayılmış olur.
\(r=2\) için sıfır olmayan iç kafes noktaları dört eksen noktası ile dört köşegen noktasından oluşur; dolayısıyla \(N=8\) ve \(H=4\) olur. Orijinden geçen ilgili dört doğru vardır ve her bir doğrunun iki ışınında da \(c=1\) nokta bulunur.
Bu doğrulardan biri için geçersiz katkı
$$1\cdot(4-1)(4-2)+1^2(8-2)+1\cdot 0\cdot(4-1)+\binom{2}{3}=6+6+0+0=12$$
çıkar. Dört doğrunun tamamı aynı davrandığı için toplam geçersiz üçlü sayısı \(4\cdot 12=48\) olur. Ayrıca
$$\binom{8}{3}=56$$
olduğundan, orijini içeren üçgen sayısı
$$56-48=8$$
olur. Bu değer, uygulamaların kullandığı küçük kontrol örneğiyle birebir aynıdır.
Bir yarım tur içindeki eş-açılı grupların çoklukları \(c_1,c_2,\dots,c_m\) olsun. Her \(c_j\), orijinden geçen bir yönsüz doğruyu temsil eder. O zaman nihai cevap
$$\boxed{\binom{N}{3}-\sum_{j=1}^{m}\left(c_j(H-c_j)(H-c_j-1)+c_j^2(N-2c_j)+c_j(c_j-1)(H-c_j)+\binom{2c_j}{3}\right).}$$
C++, Python ve Java çözümlerinin uyguladığı matematik tam olarak budur. Kaynak kodunda yalnızca ortadaki iki katkı tek bir çıkarma satırında birleştirilmiştir.
C++, Python ve Java uygulamaları önce \([-r,r]\times[-r,r]\) karesindeki bütün tam sayı noktalarını dolaşır, orijini ve çember üzerinde ya da dışında kalanları eler, sonra da kalan her nokta için \(\operatorname{atan2}(y,x)\) kutupsal açısını hesaplar. Bu açılar sıralandığında, aynı açıya sahip ardışık gruplar tam olarak aynı ışın üzerindeki noktaları verir.
Her kafes noktasının bir zıt noktası \((-x,-y)\) olduğu için, sıralı açı listesi doğal olarak \(\pi\) farkla gelen karşıt çiftlere ayrılır. Bu yüzden uygulamalar listenin yalnızca ilk yarısını tarar; böylece orijinden geçen her doğru tam bir kez ziyaret edilir. Matematiksel olarak eşit olması gereken açıları birleştirirken küçük bir tolerans kullanılır.
Koşan toplam başlangıçta \(\binom{N}{3}\) değeridir. Daha sonra her eş-açılı grup için kodda görülen üç çıkarma uygulanır: “sınırda tek köşe” terimi, “aynı ışında iki nokta veya karşıt ışınlarda birer nokta” terimi ve tam doğrusal terim \(\binom{2c}{3}\). Bütün temsilci doğrular işlendiğinde geriye tam olarak orijini sıkı biçimde içeren üçgenlerin sayısı kalır.
Kare üzerindeki tarama \((2r+1)^2\) aday noktayı kontrol eder; bu nedenle üretim aşaması \(O(r^2)\) zaman alır. \(N=|P_r|\) için \(N=\Theta(r^2)\) olduğundan, açıların sıralanması \(O(N\log N)\) maliyetlidir.
Son grup geçişi doğrusaldır, yani \(O(N)\), bellek kullanımı ise açı listesi için \(O(N)\) olur. Gerçek girdi \(r=105\) için bu yöntem çok rahattır; çünkü hiçbir yerde açık bir \(O(N^3)\) üçgen testi yapılmaz.
Definamos
$$P_r=\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}:x^2+y^2\lt r^2\}.$$
En el problema real se toma \(r=105\). Hay que contar los triángulos no ordenados cuyos tres vértices pertenecen a \(P_{105}\) y cuyo interior contiene al origen de forma estricta, no solo sobre un lado ni en una configuración degenerada.
Un enfoque directo revisaría todos los \(\binom{N}{3}\) tríos de puntos y ejecutaría una prueba geométrica de pertenencia para cada uno. Las implementaciones no hacen eso. Reordenan el conjunto por ángulo polar, agrupan los puntos que yacen sobre el mismo rayo y después restan exactamente los tríos que nunca pueden producir un triángulo válido que encierre al origen.
Un triángulo no degenerado contiene al origen si y solo si el origen pertenece a la envolvente convexa de sus tres vértices. De forma equivalente, un triángulo no contiene al origen si existe una recta que pase por el origen y deje a los tres vértices dentro de un mismo semiplano cerrado. En términos angulares, eso significa que las tres direcciones caben en un intervalo cerrado de longitud \(\pi\).
Por eso conviene contar el complemento: primero todos los tríos de puntos y luego restar los tríos cuyas direcciones caben en un semicírculo cerrado, junto con los casos colineales donde el “triángulo” tiene área cero.
Si dos puntos de la red tienen el mismo ángulo polar, entonces están sobre el mismo rayo desde el origen. Si \((u,v)\) es una dirección primitiva con \(\gcd(u,v)=1\), los puntos de ese rayo son
$$ (u,v),\ 2(u,v),\ 3(u,v),\dots $$
hasta el mayor múltiplo que todavía cumple \(k^2(u^2+v^2)\lt r^2\). Denotemos por \(c\) la cantidad de puntos en un rayo. El rayo opuesto \((-u,-v)\) tiene la misma multiplicidad \(c\), así que cada recta no orientada que pasa por el origen aporta \(2c\) puntos en total.
Sea ahora \(N=|P_r|\). Por simetría central, cada punto aparece con su opuesto, así que \(N\) es par. Escribimos
$$H=\frac{N}{2}.$$
Para una recta fija con multiplicidad \(c\) en cada uno de sus dos rayos, al quitar los \(2c\) puntos de la recta quedan \(N-2c\) puntos fuera de ella. Esos puntos se reparten por igual entre los dos semiplanos abiertos, de modo que cada lado contiene exactamente \(H-c\) puntos.
Fijemos una de esas rectas y clasifiquemos todos los tríos que fracasan en la condición de contención estricta debido a ella. Las configuraciones inválidas son disjuntas y se dividen en cuatro tipos naturales.
1. Un vértice en la frontera y dos vértices interiores del mismo lado. Elegimos un vértice en cualquiera de los dos rayos de la recta y después dos vértices del semiplano abierto del mismo lado. El recuento es
$$2c\binom{H-c}{2}=c(H-c)(H-c-1).$$
El factor \(2\) refleja que cualquiera de los dos rayos opuestos puede actuar como frontera del semicírculo cerrado mínimo.
2. Dos vértices en el mismo rayo y el tercero del mismo lado. Si dos puntos elegidos están en el mismo rayo y el tercero cae en el semiplano abierto adyacente, el origen no puede quedar dentro del triángulo. Sumando ambos rayos obtenemos
$$2\binom{c}{2}(H-c)=c(c-1)(H-c).$$
3. Un vértice en cada rayo opuesto. Entonces el segmento que une esos dos vértices pasa por el origen, de modo que el origen queda sobre un lado y no en el interior. El tercer vértice puede ser cualquier punto fuera de la recta, así que el número es
$$c^2(N-2c).$$
4. Los tres vértices en la misma recta por el origen. Son casos degenerados y aportan
$$\binom{2c}{3}.$$
Al sumar estas cuatro contribuciones sobre todas las rectas no orientadas que pasan por el origen, cada trío que no produce un triángulo válido que encierre al origen queda contado exactamente una vez.
Para \(r=2\), los puntos enteros interiores no nulos son los cuatro puntos de los ejes y los cuatro puntos diagonales. Por tanto \(N=8\) y \(H=4\). Hay cuatro rectas relevantes por el origen, y cada una tiene \(c=1\) punto en cada rayo.
Para una recta concreta, la contribución inválida es
$$1\cdot(4-1)(4-2)+1^2(8-2)+1\cdot 0\cdot(4-1)+\binom{2}{3}=6+6+0+0=12.$$
Las cuatro rectas se comportan igual, de modo que el número total de tríos inválidos es \(4\cdot 12=48\). Como
$$\binom{8}{3}=56,$$
el número de triángulos que contienen al origen es
$$56-48=8,$$
que coincide con el valor de verificación usado por las implementaciones.
Si las agrupaciones de ángulos iguales en una media vuelta tienen multiplicidades \(c_1,c_2,\dots,c_m\), entonces cada \(c_j\) representa una recta no orientada por el origen, y la respuesta final es
$$\boxed{\binom{N}{3}-\sum_{j=1}^{m}\left(c_j(H-c_j)(H-c_j-1)+c_j^2(N-2c_j)+c_j(c_j-1)(H-c_j)+\binom{2c_j}{3}\right).}$$
Esta es exactamente la matemática implementada en C++, Python y Java. En el código, las dos contribuciones centrales aparecen escritas como una sola resta combinada.
Las implementaciones en C++, Python y Java recorren todos los puntos enteros del cuadrado \([-r,r]\times[-r,r]\), descartan el origen y todos los puntos sobre o fuera del círculo, y calculan el ángulo polar \(\operatorname{atan2}(y,x)\) de cada punto restante. Al ordenar esos ángulos, cada bloque contiguo de valores iguales corresponde exactamente a un rayo desde el origen.
Como cada punto tiene su opuesto \((-x,-y)\), la lista ordenada de ángulos se descompone de manera natural en pares separados por \(\pi\). Por eso basta con recorrer la primera mitad de la lista ordenada: así se visita cada recta por el origen exactamente una vez. Durante esa fusión de ángulos iguales, las implementaciones usan una tolerancia pequeña para absorber posibles diferencias numéricas de coma flotante.
La cuenta comienza en \(\binom{N}{3}\). Para cada grupo de tamaño \(c\), la implementación evalúa las tres restas que se ven en el código: el término de “un solo vértice de frontera”, el término combinado de “dos puntos en un rayo o uno en cada rayo opuesto” y el término totalmente colineal \(\binom{2c}{3}\). Después de procesar todas las rectas representativas, el total restante es exactamente el número de triángulos que contienen al origen estrictamente en su interior.
El barrido de la rejilla examina \((2r+1)^2\) puntos candidatos, así que la fase de enumeración cuesta \(O(r^2)\). Si \(N=|P_r|\), entonces \(N=\Theta(r^2)\), y ordenar la lista de ángulos cuesta \(O(N\log N)\).
La pasada final por grupos es lineal, \(O(N)\), y la memoria usada es \(O(N)\) para almacenar los ángulos. Para el valor real \(r=105\), el método es muy cómodo porque nunca realiza una comprobación explícita de triángulos en \(O(N^3)\).
记
$$P_r=\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}:x^2+y^2\lt r^2\}.$$
在这道题的实际输入中，\(r=105\)。要求统计的是：从 \(P_{105}\) 中选出三个顶点构成的无序三角形里，有多少个三角形把原点严格包含在内部，而不是让原点落在边上，或者只得到面积为零的退化情形。
如果直接做，就要枚举全部 \(\binom{N}{3}\) 个点三元组，并对每一个都执行一次点在三角形内判定。这并不是实现所采用的方法。真正的做法是先按极角整理所有格点，再把位于同一条原点射线上的点合并成一组，最后从全部三元组里减去那些从几何上注定不可能“严格包住原点”的坏情况。
对于一个非退化三角形，原点在三角形内部，当且仅当原点位于这三个顶点的凸包之中。反过来说，如果三角形没有包含原点，那么一定存在一条经过原点的直线，使得三个顶点全部落在这条直线所确定的某个闭半平面里。用极角来描述，这就等价于三个顶点方向可以被装进一个长度为 \(\pi\) 的闭区间中。
因此最自然的做法是数补集：先取全部点三元组，再减去所有“角度落在某个闭半圆里”的三元组，以及所有三点共线、面积为零的退化情形。
如果两个格点拥有相同的极角，那么它们一定落在从原点出发的同一条射线上。设 \((u,v)\) 是一个原始格方向，满足 \(\gcd(u,v)=1\)。那么该射线上的格点恰好是
$$ (u,v),\ 2(u,v),\ 3(u,v),\dots $$
一直到最大的那个仍满足 \(k^2(u^2+v^2)\lt r^2\) 的倍数。把这条射线上的点数记作 \(c\)。与之相对的反向射线 \((-u,-v)\) 也有同样的点数 \(c\)，因此每一条经过原点的无向直线总共贡献 \(2c\) 个格点。
令 \(N=|P_r|\)。由于点集关于原点中心对称，每个点都和自己的相反点成对出现，所以 \(N\) 一定是偶数。记
$$H=\frac{N}{2}.$$
现在固定一条这样的直线，并设它两侧两个射线上的点数都是 \(c\)。把直线上的 \(2c\) 个点去掉之后，还剩下 \(N-2c\) 个点，而这些点会平均分布到这条直线两侧的两个开半平面中，因此每一侧恰好有 \(H-c\) 个点。
固定这条直线以后，把所有因为它而无法严格包含原点的三元组分类。它们彼此不重叠，正好分成四种自然情况。
1. 边界上一个顶点，同侧内部两个顶点。 先从直线的两个射线之一选出一个顶点，再从同一侧的开半平面中选出两个顶点，得到
$$2c\binom{H-c}{2}=c(H-c)(H-c-1).$$
这里的系数 \(2\) 表示：最小闭半圆的边界射线可以是这条直线的任意一个方向。
2. 同一射线上两个顶点，第三个顶点仍在这一侧。 如果两个被选中的点落在同一条射线上，而第三个点又位于这条直线同侧的开半平面中，那么原点不可能落在三角形内部。把两条相反射线都算进去，得到
$$2\binom{c}{2}(H-c)=c(c-1)(H-c).$$
3. 相反两条射线上各取一个顶点。 这时连接这两个顶点的线段会直接穿过原点，所以原点落在边上，而不是内部。第三个顶点可以是这条直线之外的任意点，因此这一类共有
$$c^2(N-2c).$$
4. 三个顶点全部在同一条经过原点的直线上。 这显然是退化情形，数量为
$$\binom{2c}{3}.$$
把这四类贡献对所有经过原点的无向直线求和，就会把每一个不能产生有效“包住原点”三角形的三元组恰好数一次。
当 \(r=2\) 时，圆内非零格点正好是四个坐标轴上的点加上四个对角点，所以 \(N=8\)，\(H=4\)。此时有四条相关的原点直线，而且每条直线的每个射线上都只有 \(c=1\) 个点。
对于其中任意一条直线，坏三元组贡献为
$$1\cdot(4-1)(4-2)+1^2(8-2)+1\cdot 0\cdot(4-1)+\binom{2}{3}=6+6+0+0=12.$$
四条直线完全对称，因此坏三元组总数是 \(4\cdot 12=48\)。而
$$\binom{8}{3}=56,$$
所以真正包含原点的三角形数目就是
$$56-48=8,$$
这与实现中使用的小规模校验值完全一致。
如果某个半转区间中的等角分组重数为 \(c_1,c_2,\dots,c_m\)，那么每一个 \(c_j\) 都对应一条经过原点的无向直线，最终答案就是
$$\boxed{\binom{N}{3}-\sum_{j=1}^{m}\left(c_j(H-c_j)(H-c_j-1)+c_j^2(N-2c_j)+c_j(c_j-1)(H-c_j)+\binom{2c_j}{3}\right).}$$
这正是 C++、Python 和 Java 实现所执行的数学内容。代码里只是把中间两项写成了一个合并的减法表达式。
C++、Python 和 Java 三个实现都会先枚举方框 \([-r,r]\times[-r,r]\) 内的所有整数点，去掉原点，以及所有落在圆上或圆外的点，然后为每个保留下来的点计算极角 \(\operatorname{atan2}(y,x)\)。把这些角排序以后，每一段连续的相等角度就正好对应一条从原点出发的射线。
由于每个格点 \((x,y)\) 都伴随着相反点 \((-x,-y)\)，排序后的角度表天然按相差 \(\pi\) 的方向成对出现。因此，实现只需要扫描有序角度表的前一半，就能够把每一条经过原点的直线恰好处理一次。在合并本应相等的角度时，程序还会使用一个很小的容差来抵消浮点数舍入误差。
运行中的答案初始为 \(\binom{N}{3}\)。随后，对每一个大小为 \(c\) 的等角分组，程序都会计算源码中出现的三次减法：一项对应“边界上只有一个顶点”，一项合并了“同射线取两个点”和“对向射线各取一个点”这两类情况，最后一项是完全共线的 \(\binom{2c}{3}\)。当所有代表性直线都处理完之后，剩下的总数就正是严格包含原点的三角形个数。
网格枚举阶段会检查 \((2r+1)^2\) 个候选格点，因此这一步的时间复杂度是 \(O(r^2)\)。如果记 \(N=|P_r|\)，则 \(N=\Theta(r^2)\)，所以排序极角的复杂度是 \(O(N\log N)\)。
最后的分组扫描是线性的，即 \(O(N)\)，而内存消耗主要来自存储角度列表，因此是 \(O(N)\)。对于题目的真实输入 \(r=105\)，这个方法非常轻松，因为它完全避免了显式的 \(O(N^3)\) 三角形逐个判定。
Обозначим
$$P_r=\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}:x^2+y^2\lt r^2\}.$$
В самой задаче берется \(r=105\). Требуется посчитать количество неупорядоченных треугольников, чьи вершины выбраны из \(P_{105}\), причем начало координат должно лежать строго внутри треугольника, а не на его стороне и не в вырожденной конфигурации.
Наивный подход перебирал бы все \(\binom{N}{3}\) тройки точек и отдельно проверял бы каждую на условие попадания начала внутрь. Реальные реализации делают иначе. Они упорядочивают точки по полярному углу, объединяют точки на одном луче и затем вычитают те тройки, которые геометрически заведомо не могут образовать треугольник, строго содержащий начало.
Невырожденный треугольник содержит начало координат тогда и только тогда, когда начало лежит в выпуклой оболочке его трех вершин. Эквивалентно: если треугольник не содержит начало, то существует прямая через начало, такая что все три вершины лежат в одной замкнутой полуплоскости. На языке углов это означает, что все три направления помещаются в некоторый замкнутый интервал длины \(\pi\).
Поэтому удобнее считать дополнение: сначала все тройки точек, а затем вычесть тройки, направления которых помещаются в один замкнутый полукруг, а также коллинеарные случаи, где площадь равна нулю.
Если два решетчатых пункта имеют один и тот же полярный угол, то они лежат на одном луче из начала. Пусть \((u,v)\) — примитивное направление, то есть \(\gcd(u,v)=1\). Тогда точки на этом луче имеют вид
$$ (u,v),\ 2(u,v),\ 3(u,v),\dots $$
до наибольшего множителя, для которого еще выполняется \(k^2(u^2+v^2)\lt r^2\). Обозначим количество таких точек на одном луче через \(c\). На противоположном луче \((-u,-v)\) их тоже ровно \(c\), так что каждая неориентированная прямая через начало дает в сумме \(2c\) точек.
Пусть теперь \(N=|P_r|\). Из центральной симметрии следует, что каждой точке соответствует противоположная, поэтому \(N\) четно. Обозначим
$$H=\frac{N}{2}.$$
Если зафиксировать одну такую прямую, на каждом ее луче лежит по \(c\) точек. После удаления этих \(2c\) точек на самой прямой остается \(N-2c\) точек, и они делятся поровну между двумя открытыми полуплоскостями. Значит, в каждой открытой полуплоскости содержится ровно \(H-c\) точек.
Зафиксируем такую прямую и разберем все тройки, которые из-за нее не могут строго содержать начало. Эти конфигурации попарно не пересекаются и распадаются на четыре естественных типа.
1. Одна граничная вершина и две внутренние вершины по одну сторону. Выбираем одну вершину на одном из двух лучей прямой, а затем две вершины из открытой полуплоскости на той же стороне. Получаем
$$2c\binom{H-c}{2}=c(H-c)(H-c-1).$$
Множитель \(2\) отвечает за выбор того, какой из двух противоположных лучей является граничным лучом минимального замкнутого полукруга.
2. Две вершины на одном луче и третья на той же стороне. Если две выбранные точки лежат на одном луче, а третья находится в соседней открытой полуплоскости, начало не может оказаться внутри треугольника. С учетом обоих лучей получаем
$$2\binom{c}{2}(H-c)=c(c-1)(H-c).$$
3. По одной вершине на противоположных лучах. Тогда отрезок между этими двумя вершинами проходит через начало, и начало лежит на стороне, а не внутри. Третью вершину можно выбрать в любой точке вне этой прямой, поэтому число таких троек равно
$$c^2(N-2c).$$
4. Все три вершины лежат на одной прямой через начало. Это вырожденные случаи, их количество равно
$$\binom{2c}{3}.$$
Если просуммировать эти четыре вклада по всем неориентированным прямым через начало, то каждая тройка, не образующая корректный треугольник с началом внутри, будет посчитана ровно один раз.
При \(r=2\) ненулевые внутренние решетчатые точки состоят из четырех осевых точек и четырех диагональных точек, так что \(N=8\), \(H=4\). Здесь есть четыре существенные прямые через начало, и на каждом их луче лежит по \(c=1\) точке.
Для одной такой прямой плохой вклад равен
$$1\cdot(4-1)(4-2)+1^2(8-2)+1\cdot 0\cdot(4-1)+\binom{2}{3}=6+6+0+0=12.$$
Все четыре прямые симметричны, значит общее число плохих троек равно \(4\cdot 12=48\). Поскольку
$$\binom{8}{3}=56,$$
то число треугольников, содержащих начало, равно
$$56-48=8,$$
и именно это значение используется как контрольное в реализациях.
Если группы одинаковых углов на одной полуокружности имеют кратности \(c_1,c_2,\dots,c_m\), то каждое \(c_j\) соответствует одной неориентированной прямой через начало, а окончательный ответ равен
$$\boxed{\binom{N}{3}-\sum_{j=1}^{m}\left(c_j(H-c_j)(H-c_j-1)+c_j^2(N-2c_j)+c_j(c_j-1)(H-c_j)+\binom{2c_j}{3}\right).}$$
Именно эту формулу реализуют решения на C++, Python и Java. В исходном коде две средние составляющие просто объединены в одну операцию вычитания.
Реализации на C++, Python и Java перебирают все целочисленные точки квадрата \([-r,r]\times[-r,r]\), отбрасывают начало координат и все точки на окружности или вне нее, а для каждой оставшейся точки вычисляют полярный угол \(\operatorname{atan2}(y,x)\). После сортировки этих углов каждый непрерывный блок одинаковых значений соответствует одному лучу из начала.
Так как каждой точке \((x,y)\) соответствует противоположная точка \((-x,-y)\), отсортированный список углов естественным образом распадается на пары направлений, отличающихся на \(\pi\). Поэтому код сканирует только первую половину списка: так каждая прямая через начало рассматривается ровно один раз. При слиянии математически равных углов используется маленький допуск, чтобы не зависеть от тонких эффектов округления в вещественной арифметике.
Текущее значение ответа стартует с \(\binom{N}{3}\). Для каждой группы размера \(c\) программа вычисляет три вычитания, которые видны в коде: вклад “одна граничная вершина”, объединенный вклад “две точки на одном луче или по одной на противоположных лучах” и полностью коллинеарный вклад \(\binom{2c}{3}\). После обработки всех представительных прямых остается ровно число треугольников, которые строго содержат начало внутри.
Перебор решетки проверяет \((2r+1)^2\) кандидатных точек, так что стадия перечисления стоит \(O(r^2)\). Если \(N=|P_r|\), то \(N=\Theta(r^2)\), а сортировка списка углов занимает \(O(N\log N)\).
Финальный проход по группам линеен, то есть \(O(N)\), а память составляет \(O(N)\) для хранения углов. Для реального значения \(r=105\) метод работает очень быстро, потому что нигде не выполняется явная проверка всех треугольников за \(O(N^3)\).
لنعرّف
$$P_r=\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}:x^2+y^2\lt r^2\}.$$
في المسألة الفعلية نأخذ \(r=105\). المطلوب هو عدّ المثلثات غير المرتبة التي تُختار رؤوسها من \(P_{105}\) وتحتوي الأصل احتواءً صارمًا في داخلها، لا أن يقع الأصل على ضلع من أضلاعها أو ضمن حالة متدهورة مساحتها صفر.
الطريقة الساذجة كانت ستفحص جميع الثلاثيات وعددها \(\binom{N}{3}\) وتطبّق اختبارًا هندسيًا لكل مثلث على حدة. أما التطبيقات الفعلية فلا تفعل ذلك إطلاقًا. هي ترتب النقاط بحسب الزاوية القطبية، ثم تجمع النقاط الواقعة على الشعاع نفسه، وبعد ذلك تطرح بالضبط الثلاثيات التي يستحيل هندسيًا أن تعطي مثلثًا يحتوي الأصل احتواءً صارمًا.
المثلث غير المتدهور يحتوي الأصل إذا وفقط إذا كان الأصل ضمن الغلاف المحدب لرؤوسه الثلاثة. وبصيغة مكافئة: إذا كان المثلث لا يحتوي الأصل، فهناك مستقيم يمر بالأصل يجعل الرؤوس الثلاثة كلها في نصف مستوى مغلق واحد. وعند ترجمة ذلك إلى الزوايا، يصبح المعنى أن الاتجاهات الثلاثة يمكن احتواؤها داخل فترة مغلقة طولها \(\pi\).
لهذا يكون عدّ المتمّم هو الطريق الأسهل: نبدأ بعدّ جميع ثلاثيات النقاط، ثم نطرح كل ثلاثية تقع اتجاهاتها داخل نصف دائرة مغلق واحد، ونطرح أيضًا الحالات الخطية التي يكون فيها “المثلث” منعدم المساحة.
إذا كان لنقطتين شبكيتين الزاوية القطبية نفسها، فهما تقعان على الشعاع نفسه الخارج من الأصل. وإذا كانت \((u,v)\) اتجاهًا أوليًا بحيث \(\gcd(u,v)=1\)، فإن نقاط ذلك الشعاع هي
$$ (u,v),\ 2(u,v),\ 3(u,v),\dots $$
حتى أكبر مضاعف ما زال يحقق \(k^2(u^2+v^2)\lt r^2\). ولنسمّ عدد هذه النقاط على شعاع واحد \(c\). وعلى الشعاع المعاكس \((-u,-v)\) يوجد العدد نفسه \(c\)، ولذلك فإن كل مستقيم غير موجّه يمر بالأصل يساهم بما مجموعه \(2c\) نقطة شبكية.
لنكتب الآن \(N=|P_r|\). وبسبب التناظر المركزي، تقترن كل نقطة بنقطتها المعاكسة، ولهذا يكون \(N\) عددًا زوجيًا. نضع
$$H=\frac{N}{2}.$$
وعند تثبيت مستقيم معيّن له \(c\) نقطة على كل من شعاعيه، فإن حذف النقاط \(2c\) الواقعة على هذا المستقيم يترك \(N-2c\) نقطة خارجه. وهذه النقاط تنقسم بالتساوي بين نصفي المستوى المفتوحين، أي إن كل جانب مفتوح يحتوي بالضبط \(H-c\) نقطة.
لنثبت الآن هذا المستقيم، ولنصنف جميع الثلاثيات التي تفشل في احتواء الأصل احتواءً صارمًا بسببه. هذه الحالات متباينة فيما بينها، وتنقسم إلى أربعة أنواع طبيعية.
1. رأس واحد على الحد، ورأسان داخليان في الجهة نفسها. نختار رأسًا واحدًا من أحد شعاعي المستقيم، ثم نختار رأسين من نصف المستوى المفتوح على الجهة نفسها، فنحصل على
$$2c\binom{H-c}{2}=c(H-c)(H-c-1).$$
العامل \(2\) يعبّر عن إمكان أن يكون الشعاع الحدّي لنصف الدائرة المغلق الأصغر هو أيًّا من الشعاعين المتقابلين.
2. رأسان على الشعاع نفسه، والثالث في الجهة نفسها. إذا كانت نقطتان مختارتان على الشعاع نفسه وكانت الثالثة في نصف المستوى المفتوح المجاور على الجهة نفسها، فلا يمكن أن يقع الأصل داخل المثلث. وبعد جمع حالتي الشعاعين نحصل على
$$2\binom{c}{2}(H-c)=c(c-1)(H-c).$$
3. رأس على كل شعاع من الشعاعين المتعاكسين. عندئذ يمر القطع الواصل بين هذين الرأسين عبر الأصل، فيقع الأصل على ضلع من أضلاع المثلث لا في داخله. أما الرأس الثالث فيمكن اختياره من أي نقطة خارج ذلك المستقيم، ومن ثم يكون العدد
$$c^2(N-2c).$$
4. الرؤوس الثلاثة كلها على المستقيم نفسه المار بالأصل. وهذه حالات متدهورة وعددها
$$\binom{2c}{3}.$$
وعند جمع هذه المساهمات الأربع على جميع المستقيمات غير الموجّهة المارة بالأصل، تُحسب كل ثلاثية لا تعطي مثلثًا صحيحًا يحتوي الأصل مرة واحدة بالضبط.
عندما يكون \(r=2\)، فإن نقاط الشبكة الداخلية غير الصفرية هي أربع نقاط على المحورين وأربع نقاط قطرية، ولذلك يكون \(N=8\) و\(H=4\). وهناك أربعة مستقيمات ذات صلة تمر بالأصل، وعلى كل شعاع من شعاعي كل مستقيم توجد نقطة واحدة فقط، أي \(c=1\).
بالنسبة إلى مستقيم واحد، تكون مساهمة الحالات غير الصالحة
$$1\cdot(4-1)(4-2)+1^2(8-2)+1\cdot 0\cdot(4-1)+\binom{2}{3}=6+6+0+0=12.$$
وجميع المستقيمات الأربعة متناظرة، لذا فإن العدد الكلي للثلاثيات غير الصالحة هو \(4\cdot 12=48\). وبما أن
$$\binom{8}{3}=56,$$
فإن عدد المثلثات التي تحتوي الأصل يساوي
$$56-48=8,$$
وهو تمامًا مقدار التحقق الصغير المستخدم في التطبيقات.
إذا كانت مجموعات الزوايا المتساوية في نصف دورة واحدة ذات تكرارات \(c_1,c_2,\dots,c_m\)، فإن كل \(c_j\) يمثل مستقيمًا غير موجّه يمر بالأصل، وتكون الإجابة النهائية
$$\boxed{\binom{N}{3}-\sum_{j=1}^{m}\left(c_j(H-c_j)(H-c_j-1)+c_j^2(N-2c_j)+c_j(c_j-1)(H-c_j)+\binom{2c_j}{3}\right).}$$
وهذه هي الرياضيات نفسها التي تنفذها حلول C++ وPython وJava. كل ما في الأمر أن الشيفرة تجمع الحدين الأوسطين داخل عملية طرح واحدة.
تقوم تطبيقات C++ وPython وJava أولًا بزيارة جميع النقاط الصحيحة داخل المربع \([-r,r]\times[-r,r]\)، ثم تستبعد الأصل وكل نقطة تقع على الدائرة أو خارجها، وتحسب الزاوية القطبية \(\operatorname{atan2}(y,x)\) لكل نقطة باقية. وبعد ترتيب هذه الزوايا، يصبح كل مقطع متصل من الزوايا المتساوية مطابقًا تمامًا لمجموعة النقاط الواقعة على شعاع واحد خارج من الأصل.
ولأن لكل نقطة شبكية النظير المعاكس \((-x,-y)\)، فإن قائمة الزوايا المرتبة تنقسم طبيعيًا إلى أزواج متقابلة يفصل بينها مقدار \(\pi\). لذلك يكفي أن تمسح التطبيقات نصف القائمة المرتبة فقط، وبهذا تعالج كل مستقيم يمر بالأصل مرة واحدة لا أكثر. وعند دمج الزوايا التي ينبغي أن تكون متساوية رياضيًا، تستخدم الشيفرة سماحية صغيرة لمقاومة آثار التقريب العددي.
تبدأ القيمة الجارية للإجابة من \(\binom{N}{3}\). ثم لكل مجموعة حجمها \(c\)، تحسب الشيفرة عمليات الطرح الثلاث الظاهرة في المصدر: حد “رأس حدّي واحد”، وحدًا مدمجًا يجمع حالتي “نقطتان على شعاع واحد” و“نقطة على كل من شعاعين متعاكسين”، ثم الحد الخطي الكامل \(\binom{2c}{3}\). وبعد إنهاء جميع المستقيمات الممثلة، يكون الباقي هو بالضبط عدد المثلثات التي تحتوي الأصل احتواءً صارمًا.
يمر مسح الشبكة على \((2r+1)^2\) نقطة مرشحة، ولذلك تكلف مرحلة التعداد \(O(r^2)\). وإذا كتبنا \(N=|P_r|\)، فإن \(N=\Theta(r^2)\)، ومن ثم يكلف ترتيب الزوايا \(O(N\log N)\).
أما المرور النهائي على المجموعات فهو خطي، أي \(O(N)\)، بينما استهلاك الذاكرة هو \(O(N)\) لتخزين قائمة الزوايا. وبالنسبة إلى القيمة الحقيقية \(r=105\)، فهذه الطريقة مريحة جدًا لأنها تتجنب تمامًا أي فحص صريح لجميع المثلثات بزمن \(O(N^3)\).