The point set is generated by
$$x_n=(1248^n \bmod 32323)-16161,\qquad y_n=(8421^n \bmod 30103)-15051,$$
and \(P_n=\{(x_1,y_1),\dots,(x_n,y_n)\}\). We must compute \(C(n)\), the number of triangles with vertices in \(P_n\) that contain the origin strictly in their interior. The published checkpoints are \(C(8)=20\), \(C(600)=8950634\), and \(C(40000)=2666610948988\).
Write a nonzero point as \(p=(x,y)\), let
$$g=\gcd(|x|,|y|),\qquad d(p)=\left(\frac{x}{g},\frac{y}{g}\right).$$
Then \(d(p)\) is the primitive lattice direction of \(p\). If \(p=r\,d\) with \(r\gt 0\), the condition that the origin lies strictly inside the triangle \(\operatorname{conv}(p_1,p_2,p_3)\) is equivalent to the existence of positive barycentric coefficients:
$$0\in \operatorname{int}\operatorname{conv}(p_1,p_2,p_3)\iff \exists \lambda_1,\lambda_2,\lambda_3\gt 0,\ \lambda_1+\lambda_2+\lambda_3=1,\ \lambda_1p_1+\lambda_2p_2+\lambda_3p_3=0.$$
After substituting \(p_t=r_t d_t\), this becomes a positive linear relation among the directions \(d_t\), so only the ray of each point matters. Therefore the implementations group equal primitive directions and store only their multiplicities. Let the distinct direction classes be \(d_1,\dots,d_m\) with weights \(w_1,\dots,w_m\).
If two chosen vertices come from the same direction class, they lie on the same ray from the origin. Such a triangle cannot strictly contain the origin, so every valid triangle must use three distinct direction classes.
The weighted number of ways to choose one point from each of three distinct direction classes is
$$T_{\mathrm{distinct}}=\sum_{1\le i\lt j\lt k\le m} w_i w_j w_k.$$
Introduce the power sums
$$W=\sum_{i=1}^{m} w_i,\qquad S_2=\sum_{i=1}^{m} w_i^2,\qquad S_3=\sum_{i=1}^{m} w_i^3.$$
Expanding \((\sum_i w_i)^3\) and collecting equal-index patterns gives the elementary symmetric sum identity
$$\boxed{T_{\mathrm{distinct}}=\frac{W^3-3WS_2+2S_3}{6}.}$$
This counts every choice from three different direction classes, regardless of whether the origin ends up inside, outside, or on the boundary.
For three distinct directions there are exactly two ways to fail the strict interior condition.
First, one pair may be opposite directions. Then the segment joining those two vertices passes through the origin, so the origin lies on the boundary of the triangle rather than in its interior.
Second, all three directions may lie inside a single open semicircle. In that case there exists a line through the origin with all three vertices on the same open side, so the origin is strictly outside the triangle.
Conversely, if there is no opposite pair and the three directions are not contained in any open semicircle, then the three rays wrap completely around the origin, which forces the origin to be strictly inside the triangle. So the answer is obtained by subtracting exactly these two invalid families from \(T_{\mathrm{distinct}}\).
Consider one unordered opposite pair \(\{d,-d\}\) with weights \(a\) and \(b\). A boundary triangle is formed by choosing one point from each of these two classes and a third point from any other class, so the contribution is
$$a\,b\,(W-a-b).$$
Summing over all unordered opposite pairs gives
$$\boxed{B=\sum_{\{d,-d\}} w_d\,w_{-d}\,(W-w_d-w_{-d}).}$$
This term removes every triple for which the origin lies on an edge.
Sort the direction classes by polar angle around the origin. The implementations do this exactly, without floating-point angles: directions are split into two half-planes, and within the same half-plane the sign of the determinant
$$\det(a,b)=a_x b_y-a_y b_x$$
determines angular order.
Fix an anchor direction \(d_i\). Move a second pointer forward while the next direction still satisfies
$$\det(d_i,d_j)\gt 0,$$
which is equivalent to saying that the angular difference from \(d_i\) is strictly between \(0\) and \(\pi\). Thus the window \(i+1,\dots,j-1\) contains exactly the directions that lie with \(d_i\) in one open semicircle.
Let
$$A_i=\sum_{k=i+1}^{j-1} w_k,\qquad Q_i=\sum_{k=i+1}^{j-1} w_k^2.$$
The weighted number of unordered pairs of distinct direction classes inside this window is
$$\sum_{i\lt u\lt v\lt j} w_u w_v=\frac{A_i^2-Q_i}{2}.$$
Multiplying by the anchor weight \(w_i\) yields the contribution of all invalid triangles whose smallest angle in circular order is \(d_i\):
$$w_i\frac{A_i^2-Q_i}{2}.$$
Every triple contained in an open semicircle is counted exactly once in this scheme, namely at its first direction in the circular order. Therefore
$$\boxed{O=\sum_{i=1}^{m} w_i\frac{A_i^2-Q_i}{2}.}$$
Subtracting both invalid contributions gives the desired count:
$$\boxed{C(n)=T_{\mathrm{distinct}}-O-B.}$$
This is the complete formula implemented in all three languages.
The C++, Python, and Java implementations generate the modular sequences iteratively, normalize each point with a greatest-common-divisor reduction, and store the resulting primitive directions. They first sort these normalized directions lexicographically so equal directions can be merged into weighted classes. From those weights they compute \(W\), \(S_2\), \(S_3\), and therefore \(T_{\mathrm{distinct}}\).
Next, the implementation searches the merged direction list for opposite classes and accumulates the boundary term \(B\). After that, the same weighted direction classes are sorted again by exact angular order. A duplicated circular array and prefix sums of \(w_i\) and \(w_i^2\) allow the two-pointer sweep to evaluate every window sum \(A_i\) and \(Q_i\) in constant time, so the open-semicircle term \(O\) is obtained in one linear scan after sorting.
Let \(n\) be the number of generated points and \(m\) the number of distinct primitive directions. Sequence generation and normalization cost \(O(n)\) time. The implementations then sort all \(n\) normalized directions before compression, so that stage costs \(O(n\log n)\) time and uses \(O(n)\) memory. Merging equal directions is \(O(n)\), finding opposite classes with ordered search is \(O(m\log m)\), sorting the \(m\) direction classes by angle is \(O(m\log m)\), and the two-pointer sweep with prefix sums is \(O(m)\). The overall running time is therefore dominated by \(O(n\log n)\), and the implemented memory usage is \(O(n)\).
Die Punktmenge wird durch
$$x_n=(1248^n \bmod 32323)-16161,\qquad y_n=(8421^n \bmod 30103)-15051$$
erzeugt, und \(P_n=\{(x_1,y_1),\dots,(x_n,y_n)\}\). Gesucht ist \(C(n)\), also die Anzahl der Dreiecke mit Ecken in \(P_n\), die den Ursprung strikt im Inneren enthalten. Die veröffentlichten Kontrollwerte sind \(C(8)=20\), \(C(600)=8950634\) und \(C(40000)=2666610948988\).
Für einen von null verschiedenen Punkt \(p=(x,y)\) setzen wir
$$g=\gcd(|x|,|y|),\qquad d(p)=\left(\frac{x}{g},\frac{y}{g}\right).$$
Dann ist \(d(p)\) die primitive Gitterrichtung von \(p\). Schreibt man \(p=r\,d\) mit \(r\gt 0\), dann ist die Bedingung, dass der Ursprung strikt im Inneren von \(\operatorname{conv}(p_1,p_2,p_3)\) liegt, äquivalent zu positiven baryzentrischen Koeffizienten:
$$0\in \operatorname{int}\operatorname{conv}(p_1,p_2,p_3)\iff \exists \lambda_1,\lambda_2,\lambda_3\gt 0,\ \lambda_1+\lambda_2+\lambda_3=1,\ \lambda_1p_1+\lambda_2p_2+\lambda_3p_3=0.$$
Nach Einsetzen von \(p_t=r_t d_t\) bleibt eine positive lineare Relation zwischen den Richtungen \(d_t\). Daher ist nur der Strahl eines Punktes relevant, nicht seine Entfernung vom Ursprung. Die Implementierungen fassen gleiche primitive Richtungen zusammen und speichern nur ihre Häufigkeiten. Die verschiedenen Richtungsklassen seien \(d_1,\dots,d_m\) mit Gewichten \(w_1,\dots,w_m\).
Werden zwei Eckpunkte aus derselben Richtungsklasse gewählt, liegen sie auf demselben Strahl durch den Ursprung. Ein solches Dreieck kann den Ursprung nicht strikt enthalten. Also muss jedes gültige Dreieck aus drei verschiedenen Richtungsklassen stammen.
Die gewichtete Anzahl der Möglichkeiten, je einen Punkt aus drei verschiedenen Richtungsklassen zu wählen, ist
$$T_{\mathrm{distinct}}=\sum_{1\le i\lt j\lt k\le m} w_i w_j w_k.$$
Dazu definieren wir
$$W=\sum_{i=1}^{m} w_i,\qquad S_2=\sum_{i=1}^{m} w_i^2,\qquad S_3=\sum_{i=1}^{m} w_i^3.$$
Durch Ausmultiplizieren von \((\sum_i w_i)^3\) und Zusammenfassen der Indexmuster erhält man
$$\boxed{T_{\mathrm{distinct}}=\frac{W^3-3WS_2+2S_3}{6}.}$$
Damit sind zunächst alle Dreierwahlen aus unterschiedlichen Richtungen gezählt, unabhängig davon, ob der Ursprung innen, außen oder auf dem Rand liegt.
Für drei verschiedene Richtungen gibt es genau zwei Arten, wie die strikte Innenbedingung scheitern kann.
Erstens kann ein Paar aus entgegengesetzten Richtungen bestehen. Dann verläuft die Strecke zwischen diesen beiden Eckpunkten durch den Ursprung, also liegt der Ursprung auf dem Rand des Dreiecks.
Zweitens können alle drei Richtungen in einem einzigen offenen Halbkreis liegen. Dann gibt es eine Gerade durch den Ursprung, auf deren offener Seite alle drei Punkte liegen; der Ursprung befindet sich also strikt außerhalb des Dreiecks.
Umgekehrt gilt: Gibt es kein Gegenrichtungs-Paar und liegen die drei Richtungen nicht in einem offenen Halbkreis, dann umlaufen die drei Strahlen den Ursprung vollständig, und der Ursprung liegt strikt im Inneren. Deshalb genügt es, genau diese beiden Fehlklassen von \(T_{\mathrm{distinct}}\) abzuziehen.
Betrachte ein ungeordnetes Gegenrichtungs-Paar \(\{d,-d\}\) mit Gewichten \(a\) und \(b\). Ein Randdreieck entsteht, wenn man je einen Punkt aus diesen beiden Klassen und einen dritten Punkt aus einer beliebigen anderen Klasse wählt. Das liefert den Beitrag
$$a\,b\,(W-a-b).$$
Über alle ungeordneten Gegenrichtungs-Paare summiert ergibt das
$$\boxed{B=\sum_{\{d,-d\}} w_d\,w_{-d}\,(W-w_d-w_{-d}).}$$
Dieser Term entfernt alle Dreier, bei denen der Ursprung auf einer Dreiecksseite liegt.
Nun werden die Richtungsklassen nach Polarwinkel sortiert. Die Implementierungen tun dies exakt ohne Gleitkommaarithmetik: Zuerst wird nach oberer und unterer Halbebene getrennt, danach entscheidet innerhalb derselben Halbebene das Vorzeichen der Determinante
$$\det(a,b)=a_x b_y-a_y b_x$$
über die Winkelreihenfolge.
Fixiere eine Anker-Richtung \(d_i\). Ein zweiter Zeiger wird so weit vorgeschoben, wie
$$\det(d_i,d_j)\gt 0$$
gilt. Das bedeutet genau, dass der Winkelabstand von \(d_i\) strikt zwischen \(0\) und \(\pi\) liegt. Das Fenster \(i+1,\dots,j-1\) enthält also genau die Richtungen, die zusammen mit \(d_i\) in einem offenen Halbkreis liegen.
Setze
$$A_i=\sum_{k=i+1}^{j-1} w_k,\qquad Q_i=\sum_{k=i+1}^{j-1} w_k^2.$$
Die gewichtete Anzahl ungeordneter Paare verschiedener Richtungsklassen in diesem Fenster ist dann
$$\sum_{i\lt u\lt v\lt j} w_u w_v=\frac{A_i^2-Q_i}{2}.$$
Mit dem Ankergewicht \(w_i\) multipliziert erhält man den Beitrag aller ungültigen Dreier, deren erster Winkel in der Kreisreihenfolge \(d_i\) ist:
$$w_i\frac{A_i^2-Q_i}{2}.$$
Jedes Dreier in einem offenen Halbkreis wird dabei genau einmal erfasst, nämlich an seiner ersten Richtung in der zyklischen Ordnung. Also
$$\boxed{O=\sum_{i=1}^{m} w_i\frac{A_i^2-Q_i}{2}.}$$
Nach Abzug beider Fehlterme ergibt sich
$$\boxed{C(n)=T_{\mathrm{distinct}}-O-B.}$$
Genau diese Formel wird in allen drei Sprachversionen des Programms umgesetzt.
Die C++-, Python- und Java-Implementierungen erzeugen die modularen Folgen iterativ, normieren jeden Punkt per ggT auf seine primitive Richtung und speichern diese Richtungen zunächst vollständig. Anschließend werden die normierten Richtungen lexikographisch sortiert, damit gleiche Richtungen zu gewichteten Klassen zusammengefasst werden können. Aus diesen Gewichten werden \(W\), \(S_2\), \(S_3\) und damit \(T_{\mathrm{distinct}}\) berechnet.
Danach sucht die Implementierung in der zusammengefassten Liste nach Gegenrichtungen und akkumuliert den Randterm \(B\). Im nächsten Schritt werden dieselben Richtungsklassen erneut, diesmal nach exakter Winkellage, sortiert. Eine duplizierte Kreisreihenfolge sowie Präfixsummen von \(w_i\) und \(w_i^2\) erlauben es, alle Fensterwerte \(A_i\) und \(Q_i\) im linearen Two-Pointer-Durchlauf zu bestimmen. So entsteht der Halbkreis-Term \(O\) ohne erneutes quadratisches Durchprobieren.
Sei \(n\) die Zahl der erzeugten Punkte und \(m\) die Zahl der verschiedenen primitiven Richtungen. Erzeugung und Normierung kosten \(O(n)\) Zeit. Danach sortieren die Implementierungen alle \(n\) normierten Richtungen vor dem Zusammenfassen; dieser Schritt kostet \(O(n\log n)\) Zeit und benötigt \(O(n)\) Speicher. Das Zusammenfassen gleicher Richtungen ist \(O(n)\), die Suche nach Gegenrichtungen in geordneter Struktur kostet \(O(m\log m)\), die Winkelsortierung \(O(m\log m)\), und der Two-Pointer-Sweep mit Präfixsummen läuft in \(O(m)\). Insgesamt wird die Laufzeit also von \(O(n\log n)\) dominiert, und der tatsächlich verwendete Speicher ist \(O(n)\).
Noktalar
$$x_n=(1248^n \bmod 32323)-16161,\qquad y_n=(8421^n \bmod 30103)-15051$$
ile üretiliyor ve \(P_n=\{(x_1,y_1),\dots,(x_n,y_n)\}\) olarak tanımlanıyor. Amaç, köşeleri \(P_n\) içinden seçilen ve orijini tam olarak iç bölgede barındıran üçgenlerin sayısı olan \(C(n)\)'yi hesaplamaktır. Yayımlanmış kontrol değerleri \(C(8)=20\), \(C(600)=8950634\) ve \(C(40000)=2666610948988\) şeklindedir.
Sıfır olmayan bir \(p=(x,y)\) noktası için
$$g=\gcd(|x|,|y|),\qquad d(p)=\left(\frac{x}{g},\frac{y}{g}\right)$$
tanımını yapalım. Böylece \(d(p)\), \(p\)'nin asal örgü yönü olur. Eğer \(p=r\,d\) ve \(r\gt 0\) ise, orijinin \(\operatorname{conv}(p_1,p_2,p_3)\) üçgeninin içinde olması pozitif barysentirik katsayılarla eşdeğerdir:
$$0\in \operatorname{int}\operatorname{conv}(p_1,p_2,p_3)\iff \exists \lambda_1,\lambda_2,\lambda_3\gt 0,\ \lambda_1+\lambda_2+\lambda_3=1,\ \lambda_1p_1+\lambda_2p_2+\lambda_3p_3=0.$$
\(p_t=r_t d_t\) yazılınca bu koşul yönler arasında pozitif lineer bağıntıya dönüşür. Dolayısıyla yalnızca noktanın hangi ışın üzerinde olduğu önemlidir; uzaklık önemli değildir. Bu yüzden implementasyonlar aynı asal yöne düşen noktaları birleştirip sadece çokluklarını saklar. Ayrık yön sınıfları \(d_1,\dots,d_m\), bunların ağırlıkları da \(w_1,\dots,w_m\) olsun.
Eğer seçilen iki köşe aynı yön sınıfından gelirse aynı ışın üzerinde kalırlar. Böyle bir üçgen orijini kesin olarak içine alamaz. Bu nedenle geçerli her üçgen üç farklı yön sınıfı kullanmak zorundadır.
Üç farklı yön sınıfından birer nokta seçmenin ağırlıklı sayısı
$$T_{\mathrm{distinct}}=\sum_{1\le i\lt j\lt k\le m} w_i w_j w_k$$
olur. Şimdi
$$W=\sum_{i=1}^{m} w_i,\qquad S_2=\sum_{i=1}^{m} w_i^2,\qquad S_3=\sum_{i=1}^{m} w_i^3$$
tanımlarını yapalım. \((\sum_i w_i)^3\) açılımındaki eş-indeks desenlerini gruplayınca
$$\boxed{T_{\mathrm{distinct}}=\frac{W^3-3WS_2+2S_3}{6}}$$
özdeşliği elde edilir. Bu değer, orijinin içeride, dışarıda veya sınırda kalmasına bakmadan tüm farklı-yön üçlülerini sayar.
Üç farklı yön için sıkı iç bölge koşulu yalnızca iki biçimde bozulabilir.
Birinci durum, yönlerden bir çiftin tam zıt olmasıdır. Bu halde iki köşeyi birleştiren doğru parçası orijinden geçer; dolayısıyla orijin üçgenin kenarı üzerindedir.
İkinci durum, üç yönün de tek bir açık yarım çember içinde kalmasıdır. Bu durumda orijinden geçen bir doğru, üç köşeyi aynı açık tarafta bırakır; yani orijin üçgenin dışındadır.
Tersine, zıt yön çifti yoksa ve üç yön tek bir açık yarım çember içine sığmıyorsa, ışınlar orijini tam olarak sarar ve orijin üçgenin içinde kalır. Bu yüzden cevap, \(T_{\mathrm{distinct}}\) değerinden tam olarak bu iki geçersiz aileyi çıkarmaktır.
\(\{d,-d\}\) biçimindeki sırasız bir zıt yön çifti düşünelim; ağırlıkları \(a\) ve \(b\) olsun. Bir sınır üçgeni, bu iki sınıftan birer nokta ve geri kalan başka herhangi bir sınıftan üçüncü bir nokta seçilerek oluşur. Katkı
$$a\,b\,(W-a-b)$$
olur. Tüm sırasız zıt yön çiftleri üzerinde toplanırsa
$$\boxed{B=\sum_{\{d,-d\}} w_d\,w_{-d}\,(W-w_d-w_{-d})}$$
elde edilir. Bu terim, orijinin bir kenar üzerinde kaldığı bütün üçlüleri çıkarır.
Yön sınıflarını kutupsal açıya göre sıralayalım. Implementasyonlar bunu kayan nokta kullanmadan, tam karşılaştırma ile yapar: önce üst ve alt yarı-düzlem ayrılır, sonra aynı yarı-düzlem içindeki sıra
$$\det(a,b)=a_x b_y-a_y b_x$$
determinantının işareti ile belirlenir.
Bir \(d_i\) yönünü çapa olarak sabitleyelim. İkinci işaretçi
$$\det(d_i,d_j)\gt 0$$
olduğu sürece ileri alınır. Bu, \(d_i\) ile \(d_j\) arasındaki açının kesin olarak \(0\) ile \(\pi\) arasında olduğu anlamına gelir. Dolayısıyla \(i+1,\dots,j-1\) penceresi, \(d_i\) ile birlikte aynı açık yarım çemberde bulunan yönlerin tam listesidir.
Şimdi
$$A_i=\sum_{k=i+1}^{j-1} w_k,\qquad Q_i=\sum_{k=i+1}^{j-1} w_k^2$$
olsun. Bu penceredeki farklı yön sınıflarından seçilen sırasız ikililerin ağırlıklı sayısı
$$\sum_{i\lt u\lt v\lt j} w_u w_v=\frac{A_i^2-Q_i}{2}$$
şeklindedir. Bunu çapa ağırlığı \(w_i\) ile çarparsak, dairesel sırada ilk açısı \(d_i\) olan tüm geçersiz üçlülerin katkısını elde ederiz:
$$w_i\frac{A_i^2-Q_i}{2}.$$
Açık yarım çember içine düşen her üçlü bu sayımda tam bir kez görünür; çünkü dairesel sıradaki ilk yönü tektir. Böylece
$$\boxed{O=\sum_{i=1}^{m} w_i\frac{A_i^2-Q_i}{2}}$$
olur.
İki geçersiz katkı çıkarıldığında aranan sayı
$$\boxed{C(n)=T_{\mathrm{distinct}}-O-B}$$
şeklinde elde edilir. Üç dildeki implementasyon da doğrudan bu formülü uygular.
C++, Python ve Java implementasyonları modüler dizileri üs alma yerine art arda çarparak üretir, her noktayı EBOB ile asal yöne indirger ve bu yönleri önce tam liste halinde saklar. Ardından normallenmiş yönler leksikografik olarak sıralanır; böylece eşit yönler birleştirilip ağırlıklı sınıflar oluşturulur. Bu ağırlıklardan \(W\), \(S_2\), \(S_3\) ve dolayısıyla \(T_{\mathrm{distinct}}\) hesaplanır.
Sonra implementasyon, birleştirilmiş liste içinde zıt yön sınıflarını arayarak \(B\) terimini toplar. Bundan sonra aynı yön sınıfları kesin açısal sıraya göre yeniden sıralanır. Dairesel sıranın iki kez yazılması ve \(w_i\) ile \(w_i^2\) için önek toplamları tutulması sayesinde her pencere için \(A_i\) ve \(Q_i\) sabit zamanda bulunur; böylece iki işaretçili süpürme ile \(O\) terimi doğrusal geçişte tamamlanır.
\(n\) üretilen nokta sayısı, \(m\) ise farklı asal yön sayısı olsun. Dizi üretimi ve normallestirme \(O(n)\) zamandır. Ardından implementasyonlar sıkıştırmadan önce tüm \(n\) normallenmiş yönü sıralar; bu adım \(O(n\log n)\) zaman ve \(O(n)\) bellek kullanır. Eşit yönleri birleştirme \(O(n)\), sıralı arama ile zıt yön bulma \(O(m\log m)\), açıya göre sıralama \(O(m\log m)\), önek toplamlı iki işaretçi taraması ise \(O(m)\) maliyetlidir. Sonuç olarak toplam süreyi \(O(n\log n)\) belirler ve uygulanan bellek kullanımı \(O(n)\)'dir.
El conjunto de puntos se define por
$$x_n=(1248^n \bmod 32323)-16161,\qquad y_n=(8421^n \bmod 30103)-15051,$$
y \(P_n=\{(x_1,y_1),\dots,(x_n,y_n)\}\). Debemos calcular \(C(n)\), el número de triángulos con vértices en \(P_n\) que contienen al origen estrictamente en su interior. Los valores de control publicados son \(C(8)=20\), \(C(600)=8950634\) y \(C(40000)=2666610948988\).
Para un punto no nulo \(p=(x,y)\), definimos
$$g=\gcd(|x|,|y|),\qquad d(p)=\left(\frac{x}{g},\frac{y}{g}\right).$$
Entonces \(d(p)\) es la dirección primitiva de la retícula. Si escribimos \(p=r\,d\) con \(r\gt 0\), la condición de que el origen esté estrictamente dentro de \(\operatorname{conv}(p_1,p_2,p_3)\) equivale a la existencia de coeficientes baricéntricos positivos:
$$0\in \operatorname{int}\operatorname{conv}(p_1,p_2,p_3)\iff \exists \lambda_1,\lambda_2,\lambda_3\gt 0,\ \lambda_1+\lambda_2+\lambda_3=1,\ \lambda_1p_1+\lambda_2p_2+\lambda_3p_3=0.$$
Al sustituir \(p_t=r_t d_t\), el problema se convierte en una dependencia lineal positiva entre las direcciones \(d_t\). Por eso solo importa el rayo de cada punto, no su distancia al origen. Las implementaciones agrupan direcciones primitivas iguales y guardan únicamente sus multiplicidades. Sean \(d_1,\dots,d_m\) las clases distintas y \(w_1,\dots,w_m\) sus pesos.
Si dos vértices elegidos pertenecen a la misma clase de dirección, ambos quedan sobre el mismo rayo. Un triángulo así no puede contener al origen estrictamente. Por tanto, todo triángulo válido usa tres clases de dirección diferentes.
El número ponderado de formas de elegir un punto de cada una de tres clases de dirección distintas es
$$T_{\mathrm{distinct}}=\sum_{1\le i\lt j\lt k\le m} w_i w_j w_k.$$
Introducimos
$$W=\sum_{i=1}^{m} w_i,\qquad S_2=\sum_{i=1}^{m} w_i^2,\qquad S_3=\sum_{i=1}^{m} w_i^3.$$
Al expandir \((\sum_i w_i)^3\) y reagrupar los casos con índices repetidos se obtiene
$$\boxed{T_{\mathrm{distinct}}=\frac{W^3-3WS_2+2S_3}{6}.}$$
Esta cantidad cuenta todas las ternas de clases distintas, sin distinguir todavía si el origen queda dentro, fuera o sobre el borde.
Para tres direcciones distintas solo hay dos maneras de fallar la condición de interior estricto.
La primera es que aparezca un par de direcciones opuestas. En ese caso, el segmento entre esos dos vértices pasa por el origen y el origen queda sobre el borde del triángulo.
La segunda es que las tres direcciones quepan dentro de un mismo semicírculo abierto. Entonces existe una recta que pasa por el origen y deja los tres vértices en el mismo lado abierto; el origen queda estrictamente fuera del triángulo.
Recíprocamente, si no hay direcciones opuestas y las tres direcciones no caben en ningún semicírculo abierto, los tres rayos rodean completamente al origen y el origen queda estrictamente dentro. Por eso basta restar exactamente esas dos familias inválidas a \(T_{\mathrm{distinct}}\).
Tomemos un par no ordenado \(\{d,-d\}\) con pesos \(a\) y \(b\). Un triángulo de borde se forma escogiendo un punto de cada una de esas clases y un tercer punto de cualquier otra clase. Su contribución es
$$a\,b\,(W-a-b).$$
Sumando sobre todos los pares opuestos no ordenados obtenemos
$$\boxed{B=\sum_{\{d,-d\}} w_d\,w_{-d}\,(W-w_d-w_{-d}).}$$
Este término elimina todos los casos en los que el origen cae sobre un lado del triángulo.
Ordenamos las clases de dirección por ángulo polar. Las implementaciones lo hacen de manera exacta, sin ángulos de punto flotante: primero separan los dos semiplanos y, dentro del mismo semiplano, usan el signo del determinante
$$\det(a,b)=a_x b_y-a_y b_x$$
para comparar el orden angular.
Fijemos una dirección ancla \(d_i\). Se avanza un segundo puntero mientras se cumpla
$$\det(d_i,d_j)\gt 0,$$
lo que equivale a que la diferencia angular entre \(d_i\) y \(d_j\) esté estrictamente entre \(0\) y \(\pi\). Así, la ventana \(i+1,\dots,j-1\) contiene exactamente las direcciones que, junto con \(d_i\), quedan en un mismo semicírculo abierto.
Definimos
$$A_i=\sum_{k=i+1}^{j-1} w_k,\qquad Q_i=\sum_{k=i+1}^{j-1} w_k^2.$$
El número ponderado de pares no ordenados de clases distintas dentro de esa ventana es
$$\sum_{i\lt u\lt v\lt j} w_u w_v=\frac{A_i^2-Q_i}{2}.$$
Multiplicar por el peso del ancla \(w_i\) da la contribución de todas las ternas inválidas cuyo primer ángulo en el orden circular es \(d_i\):
$$w_i\frac{A_i^2-Q_i}{2}.$$
Cada terna contenida en un semicírculo abierto se cuenta exactamente una vez, precisamente en su primera dirección del orden circular. Por tanto,
$$\boxed{O=\sum_{i=1}^{m} w_i\frac{A_i^2-Q_i}{2}.}$$
Al restar ambas contribuciones inválidas se obtiene
$$\boxed{C(n)=T_{\mathrm{distinct}}-O-B.}$$
Esa es exactamente la fórmula implementada en C++, Python y Java.
Las implementaciones en C++, Python y Java generan las sucesiones modulares de forma iterativa, reducen cada punto mediante el máximo común divisor y almacenan las direcciones primitivas resultantes. Primero ordenan esas direcciones de forma lexicográfica para poder fusionar las iguales en clases ponderadas. A partir de esas multiplicidades calculan \(W\), \(S_2\), \(S_3\) y con ello \(T_{\mathrm{distinct}}\).
Después, la implementación busca las clases opuestas dentro de la lista fusionada y acumula el término de borde \(B\). A continuación vuelve a ordenar las mismas clases, ahora por ángulo exacto. Un arreglo circular duplicado y las sumas prefijo de \(w_i\) y \(w_i^2\) permiten obtener \(A_i\) y \(Q_i\) en tiempo constante para cada ventana, de modo que el término \(O\) se calcula con un solo barrido lineal tras la ordenación angular.
Sea \(n\) el número de puntos generados y \(m\) el número de direcciones primitivas distintas. Generar y normalizar cuesta \(O(n)\). Luego, las implementaciones ordenan los \(n\) vectores normalizados antes de comprimirlos, así que esa etapa cuesta \(O(n\log n)\) tiempo y \(O(n)\) memoria. Fusionar iguales cuesta \(O(n)\), buscar las clases opuestas en estructura ordenada cuesta \(O(m\log m)\), ordenar por ángulo cuesta \(O(m\log m)\), y el barrido con dos punteros y sumas prefijo cuesta \(O(m)\). En consecuencia, el tiempo total está dominado por \(O(n\log n)\) y el uso de memoria real de la implementación es \(O(n)\).
点集由下式生成：
$$x_n=(1248^n \bmod 32323)-16161,\qquad y_n=(8421^n \bmod 30103)-15051,$$
并记 \(P_n=\{(x_1,y_1),\dots,(x_n,y_n)\}\)。要求计算 \(C(n)\)，也就是从 \(P_n\) 中选出三个顶点形成的三角形里，严格包含原点的个数。题目给出的校验值为 \(C(8)=20\)、\(C(600)=8950634\)、\(C(40000)=2666610948988\)。
对任意非零点 \(p=(x,y)\)，定义
$$g=\gcd(|x|,|y|),\qquad d(p)=\left(\frac{x}{g},\frac{y}{g}\right).$$
这里 \(d(p)\) 是该点对应的原始整方向。若写成 \(p=r\,d\) 且 \(r\gt 0\)，那么“原点严格位于 \(\operatorname{conv}(p_1,p_2,p_3)\) 内部”与“存在正的重心坐标”完全等价：
$$0\in \operatorname{int}\operatorname{conv}(p_1,p_2,p_3)\iff \exists \lambda_1,\lambda_2,\lambda_3\gt 0,\ \lambda_1+\lambda_2+\lambda_3=1,\ \lambda_1p_1+\lambda_2p_2+\lambda_3p_3=0.$$
把 \(p_t=r_t d_t\) 代入后，问题就变成这些方向 \(d_t\) 之间是否存在正线性关系。因此只与方向有关，与离原点的距离无关。实现里会把相同的原始方向合并，只保留每个方向出现的次数。设不同方向类为 \(d_1,\dots,d_m\)，其权重为 \(w_1,\dots,w_m\)。
如果两个顶点来自同一个方向类，它们就在同一条从原点射出的射线上。这样的三角形不可能严格包住原点，所以合法三角形一定来自三个不同的方向类。
从三个不同方向类各取一个点的加权总数为
$$T_{\mathrm{distinct}}=\sum_{1\le i\lt j\lt k\le m} w_i w_j w_k.$$
记
$$W=\sum_{i=1}^{m} w_i,\qquad S_2=\sum_{i=1}^{m} w_i^2,\qquad S_3=\sum_{i=1}^{m} w_i^3.$$
把 \((\sum_i w_i)^3\) 展开并按下标是否重复分组，可得
$$\boxed{T_{\mathrm{distinct}}=\frac{W^3-3WS_2+2S_3}{6}.}$$
这一步只是把所有不同方向类的三元组都算进去，还没有区分原点是在内部、外部还是边界上。
对三个互不相同的方向来说，严格内含条件只会以两种方式失败。
第一种是其中一对方向恰好相反。此时这两个顶点之间的线段经过原点，所以原点落在三角形边界上。
第二种是三个方向全部落在同一个开半圆内。这样就存在一条经过原点的直线，把三个顶点都放在同一侧，于是原点严格在三角形外部。
反过来，如果没有相反方向对，而且三个方向又不可能塞进任意一个开半圆，那么这三条射线会把原点完整包围，原点就严格位于三角形内部。因此答案只需要从 \(T_{\mathrm{distinct}}\) 中减去这两类无效情况。
考虑一个无序相反方向对 \(\{d,-d\}\)，其权重分别为 \(a\) 和 \(b\)。要形成边界三角形，就从这两类里各选一个点，再从其余任意其他方向类中选第三个点，因此贡献为
$$a\,b\,(W-a-b).$$
对所有无序相反方向对求和，得到
$$\boxed{B=\sum_{\{d,-d\}} w_d\,w_{-d}\,(W-w_d-w_{-d}).}$$
这个量正好删掉所有“原点落在某条边上”的三元组。
先按极角对方向类排序。实现中不使用浮点角度，而是用精确比较：先区分上半平面和下半平面，再利用行列式
$$\det(a,b)=a_x b_y-a_y b_x$$
的符号决定同一半平面内的角度顺序。
固定一个锚点方向 \(d_i\)，向前移动第二个指针，只要满足
$$\det(d_i,d_j)\gt 0$$
就继续扩张窗口。这等价于 \(d_i\) 到 \(d_j\) 的角差严格位于 \(0\) 与 \(\pi\) 之间，所以区间 \(i+1,\dots,j-1\) 恰好是与 \(d_i\) 一起落在同一开半圆中的方向。
定义
$$A_i=\sum_{k=i+1}^{j-1} w_k,\qquad Q_i=\sum_{k=i+1}^{j-1} w_k^2.$$
那么该窗口内从两个不同方向类中选点的加权无序对数为
$$\sum_{i\lt u\lt v\lt j} w_u w_v=\frac{A_i^2-Q_i}{2}.$$
再乘上锚点权重 \(w_i\)，就得到所有“按圆周顺序第一个方向是 \(d_i\)”的无效三元组贡献：
$$w_i\frac{A_i^2-Q_i}{2}.$$
任何落在某个开半圆中的三元组都会被这样恰好统计一次，也就是统计在它圆周顺序中的第一个方向处。因此
$$\boxed{O=\sum_{i=1}^{m} w_i\frac{A_i^2-Q_i}{2}.}$$
把两类无效情况都减掉，得到
$$\boxed{C(n)=T_{\mathrm{distinct}}-O-B.}$$
这就是 C++、Python 和 Java 实现共同采用的核心公式。
C++、Python 和 Java 的实现都用迭代乘法生成模序列，再用最大公因数把每个点约化成原始方向，并先把这些方向完整存储下来。随后先按字典序排序，便于把完全相同的方向压缩成带权方向类。由这些权重可直接算出 \(W\)、\(S_2\)、\(S_3\)，进而得到 \(T_{\mathrm{distinct}}\)。
接下来，实现会在压缩后的方向类列表中查找相反方向并累加边界项 \(B\)。然后再把这些方向类按精确极角顺序排序。通过把有序圆环复制一遍，并维护 \(w_i\) 与 \(w_i^2\) 的前缀和，就能在双指针扫描时用常数时间得到每个窗口的 \(A_i\) 和 \(Q_i\)，从而在线性扫描中求出 \(O\)。
设生成点数为 \(n\)，不同原始方向类个数为 \(m\)。生成与归一化需要 \(O(n)\) 时间。之后，实现会先对全部 \(n\) 个归一化方向排序再做压缩，因此这一步需要 \(O(n\log n)\) 时间和 \(O(n)\) 空间。压缩相同方向是 \(O(n)\)，在有序结构中寻找相反方向是 \(O(m\log m)\)，按角度排序是 \(O(m\log m)\)，双指针加前缀和扫描是 \(O(m)\)。所以总体时间复杂度由 \(O(n\log n)\) 主导，而当前实现的空间复杂度是 \(O(n)\)。
Множество точек задается формулами
$$x_n=(1248^n \bmod 32323)-16161,\qquad y_n=(8421^n \bmod 30103)-15051,$$
а \(P_n=\{(x_1,y_1),\dots,(x_n,y_n)\}\). Требуется вычислить \(C(n)\), то есть число треугольников с вершинами в \(P_n\), которые строго содержат начало координат. Опубликованные контрольные значения: \(C(8)=20\), \(C(600)=8950634\), \(C(40000)=2666610948988\).
Для ненулевой точки \(p=(x,y)\) положим
$$g=\gcd(|x|,|y|),\qquad d(p)=\left(\frac{x}{g},\frac{y}{g}\right).$$
Тогда \(d(p)\) есть примитивное направление на решетке. Если записать \(p=r\,d\) при \(r\gt 0\), то условие того, что начало координат строго лежит внутри \(\operatorname{conv}(p_1,p_2,p_3)\), эквивалентно существованию положительных барицентрических коэффициентов:
$$0\in \operatorname{int}\operatorname{conv}(p_1,p_2,p_3)\iff \exists \lambda_1,\lambda_2,\lambda_3\gt 0,\ \lambda_1+\lambda_2+\lambda_3=1,\ \lambda_1p_1+\lambda_2p_2+\lambda_3p_3=0.$$
После подстановки \(p_t=r_t d_t\) задача сводится к положительной линейной зависимости между направлениями \(d_t\). Значит, важен только луч, а не расстояние до начала координат. Поэтому реализации объединяют одинаковые примитивные направления и сохраняют лишь их кратности. Пусть различные классы направлений равны \(d_1,\dots,d_m\), а их веса равны \(w_1,\dots,w_m\).
Если две выбранные вершины принадлежат одному и тому же классу направления, они лежат на одном луче из начала координат. Такой треугольник не может строго содержать начало, поэтому любой допустимый треугольник обязан использовать три разные классы направлений.
Взвешенное число способов выбрать по одной точке из трех различных классов направлений равно
$$T_{\mathrm{distinct}}=\sum_{1\le i\lt j\lt k\le m} w_i w_j w_k.$$
Введем обозначения
$$W=\sum_{i=1}^{m} w_i,\qquad S_2=\sum_{i=1}^{m} w_i^2,\qquad S_3=\sum_{i=1}^{m} w_i^3.$$
Раскрытие \((\sum_i w_i)^3\) и группировка по типам совпадения индексов дают тождество
$$\boxed{T_{\mathrm{distinct}}=\frac{W^3-3WS_2+2S_3}{6}.}$$
На этом этапе учитываются все тройки различных направлений без разделения на внутренние, внешние и граничные случаи.
Для трех различных направлений строгая внутренность нарушается ровно в двух ситуациях.
Первая ситуация: одна пара направлений противоположна. Тогда отрезок между соответствующими вершинами проходит через начало координат, и начало лежит на границе треугольника.
Вторая ситуация: все три направления помещаются в один открытый полукруг. Тогда существует прямая через начало координат, оставляющая все три вершины по одну открытую сторону, следовательно, начало строго вне треугольника.
Обратно, если противоположной пары нет и три направления не помещаются ни в один открытый полукруг, то лучи обходят начало координат по кругу, и начало оказывается строго внутри треугольника. Значит, из \(T_{\mathrm{distinct}}\) нужно вычесть ровно эти две семьи неверных троек.
Рассмотрим неупорядоченную пару \(\{d,-d\}\) с весами \(a\) и \(b\). Граничный треугольник получается, если выбрать по одной точке из этих двух классов и третью точку из любого другого класса. Вклад такой пары равен
$$a\,b\,(W-a-b).$$
Суммируя по всем неупорядоченным противоположным парам, получаем
$$\boxed{B=\sum_{\{d,-d\}} w_d\,w_{-d}\,(W-w_d-w_{-d}).}$$
Этот член удаляет все тройки, в которых начало координат лежит на стороне треугольника.
Теперь упорядочим классы направлений по полярному углу. Реализации делают это точно, без использования вещественных углов: сначала отделяют верхнюю полуплоскость от нижней, а внутри одной полуплоскости сравнивают направления по знаку определителя
$$\det(a,b)=a_x b_y-a_y b_x.$$
Зафиксируем опорное направление \(d_i\). Второй указатель двигается вперед, пока выполняется
$$\det(d_i,d_j)\gt 0,$$
то есть пока угловая разность между \(d_i\) и \(d_j\) строго лежит между \(0\) и \(\pi\). Следовательно, окно \(i+1,\dots,j-1\) содержит ровно те направления, которые вместе с \(d_i\) лежат в одном открытом полукруге.
Положим
$$A_i=\sum_{k=i+1}^{j-1} w_k,\qquad Q_i=\sum_{k=i+1}^{j-1} w_k^2.$$
Тогда взвешенное число неупорядоченных пар различных направлений внутри этого окна равно
$$\sum_{i\lt u\lt v\lt j} w_u w_v=\frac{A_i^2-Q_i}{2}.$$
Умножая на вес якоря \(w_i\), получаем вклад всех неверных троек, у которых первым направлением в круговом порядке является \(d_i\):
$$w_i\frac{A_i^2-Q_i}{2}.$$
Каждая тройка, лежащая в открытом полукруге, учитывается ровно один раз, а именно в своей первой по кругу точке. Поэтому
$$\boxed{O=\sum_{i=1}^{m} w_i\frac{A_i^2-Q_i}{2}.}$$
После вычитания обеих неверных частей получаем
$$\boxed{C(n)=T_{\mathrm{distinct}}-O-B.}$$
Именно эта формула реализована в версиях на C++, Python и Java.
Реализации на C++, Python и Java порождают модульные последовательности итеративно, затем сокращают каждую точку по наибольшему общему делителю до примитивного направления и сначала сохраняют все такие направления целиком. После этого нормализованные направления сортируются лексикографически, чтобы одинаковые можно было объединить в взвешенные классы. По этим весам вычисляются \(W\), \(S_2\), \(S_3\) и затем \(T_{\mathrm{distinct}}\).
Далее реализация ищет в сжатом списке противоположные направления и накапливает граничный член \(B\). Затем те же классы направлений сортируются уже по точному углу. Дублирование кругового порядка и префиксные суммы для \(w_i\) и \(w_i^2\) позволяют получать \(A_i\) и \(Q_i\) за \(O(1)\) на окно, так что величина \(O\) вычисляется одним линейным двухуказательным проходом после сортировки.
Пусть \(n\) обозначает число сгенерированных точек, а \(m\) — число различных примитивных направлений. Генерация и нормализация требуют \(O(n)\) времени. Затем реализации сортируют все \(n\) нормализованных направлений до сжатия, поэтому этот этап стоит \(O(n\log n)\) времени и \(O(n)\) памяти. Объединение одинаковых направлений занимает \(O(n)\), поиск противоположных классов в упорядоченном списке — \(O(m\log m)\), сортировка по углу — \(O(m\log m)\), а sweep с двумя указателями и префиксными суммами — \(O(m)\). Следовательно, итоговая асимптотика определяется членом \(O(n\log n)\), а фактически используемая память равна \(O(n)\).
تُولَّد مجموعة النقاط بالعلاقتين
$$x_n=(1248^n \bmod 32323)-16161,\qquad y_n=(8421^n \bmod 30103)-15051,$$
ثم نعرّف \(P_n=\{(x_1,y_1),\dots,(x_n,y_n)\}\). المطلوب هو حساب \(C(n)\)، أي عدد المثلثات التي رؤوسها من \(P_n\) وتحتوي الأصل احتواءً صارمًا في داخلها. القيم المرجعية المنشورة هي \(C(8)=20\)، و\(C(600)=8950634\)، و\(C(40000)=2666610948988\).
لكل نقطة غير صفرية \(p=(x,y)\) نعرّف
$$g=\gcd(|x|,|y|),\qquad d(p)=\left(\frac{x}{g},\frac{y}{g}\right).$$
هنا \(d(p)\) هو الاتجاه الشبكي البدائي للنقطة. وإذا كتبنا \(p=r\,d\) حيث \(r\gt 0\)، فإن شرط وجود الأصل داخل \(\operatorname{conv}(p_1,p_2,p_3)\) بشكل صارم يكافئ وجود معاملات باريцентрية موجبة:
$$0\in \operatorname{int}\operatorname{conv}(p_1,p_2,p_3)\iff \exists \lambda_1,\lambda_2,\lambda_3\gt 0,\ \lambda_1+\lambda_2+\lambda_3=1,\ \lambda_1p_1+\lambda_2p_2+\lambda_3p_3=0.$$
بعد التعويض \(p_t=r_t d_t\) تصبح المسألة علاقة خطية موجبة بين الاتجاهات \(d_t\). لذلك لا تهمنا المسافة عن الأصل، بل يهم فقط الشعاع الذي تقع عليه النقطة. ولهذا تجمع التطبيقات الاتجاهات البدائية المتطابقة وتحتفظ فقط بعدد مرات ظهور كل اتجاه. لنرمز إلى فئات الاتجاهات المختلفة بـ \(d_1,\dots,d_m\)، وأوزانها بـ \(w_1,\dots,w_m\).
إذا اختير رأسان من الفئة نفسها فهما يقعان على الشعاع نفسه الخارج من الأصل، ومثل هذا المثلث لا يمكن أن يحتوي الأصل احتواءً داخليًا صارمًا. إذن كل مثلث صالح يجب أن يستخدم ثلاث فئات اتجاه مختلفة.
عدد الطرق الموزون لاختيار نقطة واحدة من كل واحدة من ثلاث فئات اتجاه مختلفة هو
$$T_{\mathrm{distinct}}=\sum_{1\le i\lt j\lt k\le m} w_i w_j w_k.$$
ونعرّف
$$W=\sum_{i=1}^{m} w_i,\qquad S_2=\sum_{i=1}^{m} w_i^2,\qquad S_3=\sum_{i=1}^{m} w_i^3.$$
وبتوسيع \((\sum_i w_i)^3\) ثم تجميع الأنماط حسب تكرار الفهارس نحصل على
$$\boxed{T_{\mathrm{distinct}}=\frac{W^3-3WS_2+2S_3}{6}.}$$
هذا الحد يحصي كل ثلاثية من فئات مختلفة، سواء كان الأصل داخل المثلث أو خارجه أو على حدّه.
عندما تكون الاتجاهات الثلاثة مختلفة فهناك حالتان فقط تفشلان فيهما شرط الاحتواء الصارم.
الحالة الأولى هي وجود زوج من الاتجاهات المتعاكسة. عندها يمر الضلع الواصل بين هذين الرأسين عبر الأصل، فيقع الأصل على حد المثلث لا في داخله.
الحالة الثانية هي أن تقع الاتجاهات الثلاثة كلها داخل نصف دائرة مفتوح واحد. عندئذ توجد مستقيمات تمر بالأصل وتترك الرؤوس الثلاثة في الجهة المفتوحة نفسها، فيكون الأصل خارج المثلث بشكل صارم.
وبالعكس، إذا لم يوجد زوج متعاكس ولم تستطع الاتجاهات الثلاثة أن تدخل في أي نصف دائرة مفتوح، فإن الأشعة الثلاثة تطوّق الأصل بالكامل، فيقع الأصل داخل المثلث. لذلك يكفي أن نطرح هاتين العائلتين غير الصالحتين من \(T_{\mathrm{distinct}}\).
لنأخذ زوجًا غير مرتب \(\{d,-d\}\) له وزنان \(a\) و\(b\). يتكوّن مثلث حدّي باختيار نقطة من كل فئة من هاتين الفئتين ثم اختيار نقطة ثالثة من أي فئة أخرى، ولذلك تكون المساهمة
$$a\,b\,(W-a-b).$$
وبالجمع على جميع الأزواج المتعاكسة غير المرتبة نحصل على
$$\boxed{B=\sum_{\{d,-d\}} w_d\,w_{-d}\,(W-w_d-w_{-d}).}$$
وهذا الحد يزيل كل ثلاثية يكون فيها الأصل على أحد أضلاع المثلث.
نرتب فئات الاتجاه حسب الزاوية القطبية. وتنفذ التطبيقات ذلك بدقة تامة ومن دون زوايا عائمة: أولًا تقسّم الاتجاهات إلى نصفي مستوى، ثم داخل نصف المستوى نفسه يُستخدم إشارة المحدد
$$\det(a,b)=a_x b_y-a_y b_x$$
لتحديد الترتيب الزاوي.
لنثبت اتجاهًا مرساة \(d_i\). ثم نحرّك المؤشر الثاني ما دام
$$\det(d_i,d_j)\gt 0,$$
وهذا يعني أن الفرق الزاوي بين \(d_i\) و\(d_j\) يقع بدقة بين \(0\) و\(\pi\). إذن النافذة \(i+1,\dots,j-1\) تحتوي تمامًا الاتجاهات التي تقع مع \(d_i\) داخل نصف دائرة مفتوح واحد.
نعرّف
$$A_i=\sum_{k=i+1}^{j-1} w_k,\qquad Q_i=\sum_{k=i+1}^{j-1} w_k^2.$$
وعندئذ يكون عدد الأزواج غير المرتبة الموزون من فئات مختلفة داخل هذه النافذة هو
$$\sum_{i\lt u\lt v\lt j} w_u w_v=\frac{A_i^2-Q_i}{2}.$$
وبضرب ذلك في وزن المرساة \(w_i\) نحصل على مساهمة جميع الثلاثيات غير الصالحة التي يكون أول اتجاه لها في الترتيب الدائري هو \(d_i\):
$$w_i\frac{A_i^2-Q_i}{2}.$$
كل ثلاثية تقع داخل نصف دائرة مفتوح تُحصى مرة واحدة فقط، وذلك عند أول اتجاه لها في الترتيب الدائري. ومن ثم
$$\boxed{O=\sum_{i=1}^{m} w_i\frac{A_i^2-Q_i}{2}.}$$
بعد طرح الحدّين غير الصالحين نحصل على
$$\boxed{C(n)=T_{\mathrm{distinct}}-O-B.}$$
وهذه هي الصيغة التي تعتمدها تطبيقات C++ وPython وJava.
تنشئ تطبيقات C++ وPython وJava المتتاليات المعيارية على نحو تكراري، ثم تختزل كل نقطة باستخدام القاسم المشترك الأكبر إلى اتجاه بدائي، وتخزن الاتجاهات الناتجة أولًا كاملة. بعد ذلك تُرتَّب الاتجاهات المختزلة ترتيبًا معجميًا حتى يمكن دمج الاتجاهات المتساوية في فئات موزونة. ومن هذه الأوزان تُحسب القيم \(W\) و\(S_2\) و\(S_3\)، ثم يُستخرج منها \(T_{\mathrm{distinct}}\).
بعد ذلك تبحث التطبيقات عن الفئات المتعاكسة داخل القائمة المدمجة لتجميع الحد \(B\). ثم تعيد ترتيب الفئات نفسها بحسب الزاوية الدقيقة. ويسمح تكرار الترتيب الدائري مرة ثانية مع مجاميع بادئة لـ \(w_i\) و\(w_i^2\) بحساب \(A_i\) و\(Q_i\) في زمن ثابت لكل نافذة، ولذلك يُحسب الحد \(O\) بمسح خطي واحد بعد الفرز الزاوي.
ليكن \(n\) عدد النقاط المتولدة و\(m\) عدد فئات الاتجاهات البدائية المختلفة. توليد النقاط وتطبيعها يكلف \(O(n)\) زمنًا. بعد ذلك ترتب التطبيقات جميع الاتجاهات المطبعة وعددها \(n\) قبل مرحلة الدمج، وهذه الخطوة تكلف \(O(n\log n)\) زمنًا و\(O(n)\) ذاكرة. دمج الاتجاهات المتساوية هو \(O(n)\)، والبحث عن الفئات المتعاكسة في بنية مرتبة هو \(O(m\log m)\)، والفرز حسب الزاوية هو \(O(m\log m)\)، أما المسح ثنائي المؤشر مع المجاميع البادئة فهو \(O(m)\). لذلك يهيمن الحد \(O(n\log n)\) على الزمن الكلي، بينما الذاكرة المستخدمة فعليًا في التنفيذ هي \(O(n)\).