Let \(r\) be divisible by 4 and set \(a=r/4\). The fixed vertices are \(O=(0,0)\) and \(C=(a,a)\). The third vertex \(B=(x,y)\) ranges over all lattice points in the taxicab diamond
$$|x|+|y|\le r.$$
The task is to count how many non-degenerate triangles \(OBC\) are obtuse. The geometric difficulty is that the allowed points form an \(L_1\)-ball rather than a Euclidean circle, while the obtuse-angle test itself is Euclidean. The implementations resolve this by splitting the count according to which vertex is obtuse and then converting the only nonlinear case into a lattice-point count inside a circle with a parity restriction.
A triangle is obtuse exactly when one of its angles has negative dot product. With \(B=(x,y)\) and \(C=(a,a)\), the three angle tests are
$$\overrightarrow{OB}\cdot\overrightarrow{OC}=a(x+y),$$
$$\overrightarrow{CO}\cdot\overrightarrow{CB}=2a^2-a(x+y),$$
$$\overrightarrow{BO}\cdot\overrightarrow{BC}=x^2+y^2-a(x+y).$$
Therefore the triangle is obtuse at
$$O \iff x+y \lt 0,$$
$$C \iff x+y \gt 2a=\frac r2,$$
$$B \iff x^2+y^2-a(x+y) \lt 0.$$
These three regions can be counted separately, because a non-degenerate triangle cannot have more than one obtuse angle. The only overlap that matters is the collinear line \(y=x\), which will be removed at the end.
The diamond \( |x|+|y|\le r \) contains
$$1+2r(r+1)=2r^2+2r+1$$
lattice points in total. The boundary line between \(x+y \lt 0\) and \(x+y \gt 0\) is \(x+y=0\), whose lattice points are \((t,-t)\) with \(|t|\le r/2\), so it contributes exactly \(r+1\) points.
By symmetry of the diamond across the line \(x+y=0\), the strict half-plane \(x+y \lt 0\) contains half of the remaining points:
$$N_O=\frac{(2r^2+2r+1)-(r+1)}{2}=r^2+\frac r2.$$
This is the first closed-form term used by the implementations.
For the inequality \(x+y \gt r/2\), it is convenient to switch to diagonal coordinates
$$p=x+y,\qquad q=x-y.$$
Because \(x=(p+q)/2\) and \(y=(p-q)/2\), the lattice condition becomes \(p\equiv q\pmod 2\), and the diamond condition becomes
$$|p|\le r,\qquad |q|\le r.$$
Now fix a diagonal level \(p=s\) with \(r/2 \lt s\le r\). The allowed points on that level are exactly the integers \(q\in[-r,r]\) with the same parity as \(s\). When \(s\) is even there are \(r+1\) such values of \(q\); when \(s\) is odd there are \(r\).
Since \(r\) is divisible by 4, the levels \(s=r/2+1,r/2+2,\dots,r\) contain exactly \(r/4\) even values and \(r/4\) odd values. Hence
$$N_C=\frac r4(r+1)+\frac r4 r=\frac{r(2r+1)}{4}.$$
This is the second closed-form term.
The third condition is the only nonlinear one:
$$x^2+y^2-a(x+y) \lt 0.$$
Completing the square gives
$$\left(x-\frac a2\right)^2+\left(y-\frac a2\right)^2 \lt \frac{a^2}{2},$$
or, after multiplying by 4,
$$ (2x-a)^2+(2y-a)^2 \lt 2a^2. $$
So the points with an obtuse angle at \(B\) are exactly the lattice points strictly inside the circle whose diameter is \(OC\). The implementations use the scaled coordinates
$$u=2x-a,\qquad v=2y-a,$$
because then \(u\) and \(v\) are integers and both have the same parity as \(a\). Since the left-hand side is an integer, the strict inequality is equivalent to
$$u^2+v^2\le 2a^2-1.$$
Thus \(N_B\) is a lattice-circle count with a fixed parity pattern. The code scans admissible nonnegative \(u\)-values in steps of 2, keeps the largest same-parity \(v\) satisfying the circle inequality, and moves that \(v\)-pointer only downward. If the current maximum is \(v\), then the number of signed same-parity values from \(-v\) to \(v\) is \(v+1\), and the column contributes once when \(u=0\) and twice when \(u\ne 0\) because of the symmetry \(u\leftrightarrow -u\).
Here \(a=2\). The three main pieces are
$$N_O=8^2+\frac 82=68,\qquad N_C=\frac{8(17)}{4}=34.$$
For the \(B\)-obtuse region, the inequality becomes
$$x^2+y^2-2(x+y)\lt 0\iff (x-1)^2+(y-1)^2\lt 2.$$
The integer points strictly inside that circle are
$$ (1,0),\ (0,1),\ (1,1),\ (2,1),\ (1,2), $$
so \(N_B=5\). One of them, namely \((1,1)\), lies on the line \(y=x\) and is degenerate. After the global correction discussed below, the total becomes
$$68+34+5-7=100,$$
which matches the small checkpoint used by the implementations.
All points \(B=(t,t)\) with \(-r/2\le t\le r/2\) are collinear with \(O\) and \(C\), so they do not form valid triangles. Two of these points, \(t=0\) and \(t=a\), are \(O\) and \(C\) themselves and were never counted, because the corresponding dot products are zero rather than negative.
Every other point on \(y=x\) was counted exactly once by the three cases above:
$$t\lt 0 \Rightarrow \text{counted in }N_O,$$
$$0\lt t\lt a \Rightarrow \text{counted in }N_B,$$
$$t\gt a \Rightarrow \text{counted in }N_C.$$
The number of such points is
$$\frac r2+\left(\frac r4-1\right)+\frac r4=r-1.$$
Therefore the final formula is
$$N(r)=N_O+N_C+N_B-(r-1).$$
The C++, Python, and Java implementations first compute \(a=r/4\), then evaluate the two closed-form contributions \(N_O=r^2+r/2\) and \(N_C=r(2r+1)/4\) directly with integer arithmetic. No floating-point geometry is needed for those parts.
The only iterative part is \(N_B\). The implementation converts the problem to \(u^2+v^2\le 2a^2-1\) with \(u\equiv v\equiv a\pmod 2\). It finds the initial admissible \(v\) with an integer square root, iterates over admissible \(u\)-values in steps of 2, and shrinks \(v\) only when the current pair lies outside the circle. Because the maximum feasible \(v\) never increases as \(u\) increases, this is a monotone sweep rather than a two-dimensional search.
For each accepted \(u\), the implementation adds \(v+1\) same-parity values of \(v\) and doubles the contribution unless \(u=0\). After that it subtracts the universal degeneracy correction \(r-1\). The C++ implementation also includes small-radius checkpoint tests and can split the \(u\)-range across worker threads, while the Python and Java implementations perform the same mathematics serially.
The two linear-half-plane counts and the final degeneracy correction are \(O(1)\). The circle phase examines only admissible \(u\)-values, so its outer loop has \(O(a)\) iterations, and the \(v\)-pointer moves downward at most \(O(a)\) times overall. Hence the total running time is \(O(a)=O(r)\), with \(a=r/4\).
The memory usage is \(O(1)\) for the serial implementations and still \(O(1)\) extra per worker in the threaded C++ variant. The key optimization is that the circle is never sampled point by point; instead, each admissible \(u\)-column is counted in one step after locating its topmost valid \(v\).
Sei \(r\) durch 4 teilbar und \(a=r/4\). Die festen Eckpunkte sind \(O=(0,0)\) und \(C=(a,a)\). Der dritte Eckpunkt \(B=(x,y)\) läuft über alle Gitterpunkte im Taxi-Diamanten
$$|x|+|y|\le r.$$
Gesucht ist die Anzahl der nicht ausgearteten stumpfwinkligen Dreiecke \(OBC\). Die Schwierigkeit liegt darin, dass die zulässigen Punkte durch eine \(L_1\)-Geometrie beschrieben werden, der Stumpfwinkeltest aber euklidisch ist. Die Lösung zerlegt deshalb die Menge nach dem stumpfen Eckpunkt und formt den einzigen nichtlinearen Fall in ein Kreis-Gitterpunktproblem mit Paritätsbedingung um.
Ein Dreieck ist genau dann stumpfwinklig, wenn für einen seiner Innenwinkel das zugehörige Skalarprodukt negativ ist. Mit \(B=(x,y)\) und \(C=(a,a)\) erhält man
$$\overrightarrow{OB}\cdot\overrightarrow{OC}=a(x+y),$$
$$\overrightarrow{CO}\cdot\overrightarrow{CB}=2a^2-a(x+y),$$
$$\overrightarrow{BO}\cdot\overrightarrow{BC}=x^2+y^2-a(x+y).$$
Daraus folgen die drei Fälle
$$O \iff x+y \lt 0,$$
$$C \iff x+y \gt 2a=\frac r2,$$
$$B \iff x^2+y^2-a(x+y) \lt 0.$$
Diese Bereiche dürfen getrennt gezählt werden, denn ein nicht ausgeartetes Dreieck kann höchstens einen stumpfen Winkel besitzen. Nur die kollineare Gerade \(y=x\) muss am Ende noch herausgerechnet werden.
Der Diamant \( |x|+|y|\le r \) enthält insgesamt
$$1+2r(r+1)=2r^2+2r+1$$
Gitterpunkte. Die Trennlinie zwischen \(x+y \lt 0\) und \(x+y \gt 0\) ist \(x+y=0\). Ihre Gitterpunkte haben die Form \((t,-t)\) mit \(|t|\le r/2\), also genau \(r+1\) Punkte.
Wegen der Symmetrie des Diamanten bezüglich dieser Diagonalen liegt die Hälfte der übrigen Punkte in der strikten Halbebene \(x+y \lt 0\):
$$N_O=\frac{(2r^2+2r+1)-(r+1)}{2}=r^2+\frac r2.$$
Das ist der erste geschlossene Summand der Implementierungen.
Für die Ungleichung \(x+y \gt r/2\) sind diagonale Koordinaten besonders praktisch:
$$p=x+y,\qquad q=x-y.$$
Aus \(x=(p+q)/2\) und \(y=(p-q)/2\) folgt die Gitterbedingung \(p\equiv q\pmod 2\), und der Diamant wird zu
$$|p|\le r,\qquad |q|\le r.$$
Fixiere nun eine Diagonale \(p=s\) mit \(r/2 \lt s\le r\). Auf dieser Ebene sind genau die ganzzahligen \(q\)-Werte aus \([-r,r]\) erlaubt, die dieselbe Parität wie \(s\) besitzen. Für gerades \(s\) gibt es \(r+1\) solche Werte, für ungerades \(s\) genau \(r\).
Da \(r\) durch 4 teilbar ist, enthält der Bereich \(s=r/2+1,\dots,r\) genau \(r/4\) gerade und \(r/4\) ungerade Ebenen. Also
$$N_C=\frac r4(r+1)+\frac r4 r=\frac{r(2r+1)}{4}.$$
Damit ist auch der zweite lineare Beitrag geschlossen bestimmt.
Die dritte Bedingung lautet
$$x^2+y^2-a(x+y) \lt 0.$$
Durch quadratische Ergänzung erhält man
$$\left(x-\frac a2\right)^2+\left(y-\frac a2\right)^2 \lt \frac{a^2}{2},$$
also nach Multiplikation mit 4
$$ (2x-a)^2+(2y-a)^2 \lt 2a^2. $$
Geometrisch bedeutet das: \(B\) liegt strikt innerhalb des Kreises mit Durchmesser \(OC\). Die Implementierungen verwenden die skalierten Koordinaten
$$u=2x-a,\qquad v=2y-a,$$
denn dann sind \(u\) und \(v\) ganzzahlig und haben beide dieselbe Parität wie \(a\). Weil die linke Seite ganzzahlig ist, ist die strikte Ungleichung äquivalent zu
$$u^2+v^2\le 2a^2-1.$$
Damit wird \(N_B\) zu einem Kreis-Gitterpunktproblem mit fester Parität. Der Code läuft über nichtnegative zulässige \(u\)-Werte in Zweierschritten, hält den größten zulässigen gleichparigen \(v\)-Wert fest und verschiebt diesen Zeiger nur nach unten. Ist der aktuelle Höchstwert \(v\), dann gibt es genau \(v+1\) signierte gleichparige Werte zwischen \(-v\) und \(v\); für \(u=0\) wird einmal gezählt, sonst wegen der Symmetrie \(u\leftrightarrow -u\) doppelt.
Hier ist \(a=2\). Die beiden geschlossenen Beiträge sind
$$N_O=8^2+\frac 82=68,\qquad N_C=\frac{8(17)}{4}=34.$$
Für den stumpfen Winkel bei \(B\) wird die Ungleichung zu
$$x^2+y^2-2(x+y)\lt 0\iff (x-1)^2+(y-1)^2\lt 2.$$
Strikt innerhalb dieses Kreises liegen die fünf Gitterpunkte
$$ (1,0),\ (0,1),\ (1,1),\ (2,1),\ (1,2). $$
Also ist \(N_B=5\). Einer davon, nämlich \((1,1)\), liegt auf \(y=x\) und ist deshalb entartet. Nach der globalen Korrektur bleibt
$$68+34+5-7=100,$$
genau der kleine Testwert, den die Implementierungen prüfen.
Alle Punkte \(B=(t,t)\) mit \(-r/2\le t\le r/2\) liegen mit \(O\) und \(C\) auf einer Geraden und bilden daher kein gültiges Dreieck. Zwei dieser Punkte, \(t=0\) und \(t=a\), sind \(O\) beziehungsweise \(C\) selbst und wurden ohnehin nie mitgezählt, weil die betreffenden Skalarprodukte dort null und nicht negativ sind.
Jeder andere Punkt auf \(y=x\) wurde genau einmal erfasst:
$$t\lt 0 \Rightarrow \text{in }N_O,$$
$$0\lt t\lt a \Rightarrow \text{in }N_B,$$
$$t\gt a \Rightarrow \text{in }N_C.$$
Ihre Anzahl ist
$$\frac r2+\left(\frac r4-1\right)+\frac r4=r-1.$$
Damit lautet die Endformel
$$N(r)=N_O+N_C+N_B-(r-1).$$
Die C++-, Python- und Java-Implementierungen berechnen zuerst \(a=r/4\) und werten dann die beiden geschlossenen Beiträge \(N_O=r^2+r/2\) und \(N_C=r(2r+1)/4\) direkt mit Ganzzahlarithmetik aus. Für diese beiden Teile ist keinerlei geometrische Iteration nötig.
Iterativ ist nur \(N_B\). Dazu wird das Problem in die Form \(u^2+v^2\le 2a^2-1\) mit der Paritätsbedingung \(u\equiv v\equiv a\pmod 2\) überführt. Ein ganzzahliges Wurzelziehen liefert den Anfangswert für \(v\); anschließend wächst \(u\) in Zweierschritten und \(v\) wird nur dann verringert, wenn das aktuelle Paar außerhalb des Kreises liegt. Weil der maximal mögliche \(v\)-Wert mit wachsendem \(u\) nie wieder steigt, genügt ein monotoner Sweep.
Für jedes akzeptierte \(u\) addiert die Implementierung \(v+1\) zulässige \(v\)-Werte und verdoppelt den Beitrag, außer im Symmetriezentrum \(u=0\). Danach wird die universelle Korrektur \(r-1\) abgezogen. Die C++-Version enthält zusätzlich kleine Kontrolltests und kann den \(u\)-Bereich auf mehrere Threads verteilen; Python und Java verwenden dieselbe Mathematik seriell.
Die beiden linearen Halbebenen und die Ausartungskorrektur kosten \(O(1)\). Die Kreisphase betrachtet nur zulässige \(u\)-Werte, also \(O(a)\) Iterationen, und der \(v\)-Zeiger sinkt insgesamt ebenfalls nur \(O(a)\)-mal. Damit beträgt die Gesamtlaufzeit \(O(a)=O(r)\) bei \(a=r/4\).
Der Speicherverbrauch ist \(O(1)\) in den seriellen Varianten und bleibt auch in der Thread-Version pro Worker konstant. Entscheidend ist, dass nicht jeder Kreisgitterpunkt einzeln getestet wird; stattdessen wird jede zulässige \(u\)-Spalte nach Bestimmung ihres höchsten gültigen \(v\) in einem Schritt gezählt.
\(r\) sayısı 4'ün katı olsun ve \(a=r/4\) tanımlansın. Sabit köşeler \(O=(0,0)\) ve \(C=(a,a)\) noktalarıdır. Üçüncü köşe \(B=(x,y)\),
$$|x|+|y|\le r$$
elmasındaki bütün kafes noktaları üzerinde dolaşır. Amaç, dejenere olmayan kaç tane \(OBC\) üçgeninin geniş açılı olduğunu bulmaktır. Zor kısım, uygun noktaların \(L_1\) normuyla tanımlanması fakat geniş açı testinin Öklidyen olmasıdır. Çözüm bu yüzden sayımı geniş açının hangi köşede oluştuğuna göre böler ve doğrusal olmayan tek parçayı parite kısıtlı bir çember içi nokta sayımına indirger.
Bir üçgen, ancak ve ancak köşelerinden birindeki iççarpım negatife düşerse geniş açılıdır. \(B=(x,y)\) ve \(C=(a,a)\) için üç test şunlardır:
$$\overrightarrow{OB}\cdot\overrightarrow{OC}=a(x+y),$$
$$\overrightarrow{CO}\cdot\overrightarrow{CB}=2a^2-a(x+y),$$
$$\overrightarrow{BO}\cdot\overrightarrow{BC}=x^2+y^2-a(x+y).$$
Buna göre üçgenin geniş açısı
$$O \iff x+y \lt 0,$$
$$C \iff x+y \gt 2a=\frac r2,$$
$$B \iff x^2+y^2-a(x+y) \lt 0$$
koşullarından biriyle belirlenir. Dejenere olmayan bir üçgen en fazla bir geniş açıya sahip olabileceği için bu üç bölge ayrı ayrı sayılabilir. Yalnızca \(y=x\) doğrusu üzerindeki doğrusal durumları en sonda çıkarmak gerekir.
\(|x|+|y|\le r\) elmasının toplam kafes nokta sayısı
$$1+2r(r+1)=2r^2+2r+1$$
olur. \(x+y \lt 0\) ve \(x+y \gt 0\) yarı düzlemlerini ayıran çizgi \(x+y=0\)'dır. Bu doğru üzerindeki noktalar \((t,-t)\) biçimindedir ve \(|t|\le r/2\) olduğundan tam \(r+1\) adettir.
Elmas bu doğruya göre simetriktir; dolayısıyla çizgi üzerindekiler çıkarıldıktan sonra kalan noktaların yarısı \(x+y \lt 0\) tarafındadır:
$$N_O=\frac{(2r^2+2r+1)-(r+1)}{2}=r^2+\frac r2.$$
Uygulamadaki ilk kapalı form terim budur.
\(x+y \gt r/2\) eşitsizliği için çapraz koordinatlar çok kullanışlıdır:
$$p=x+y,\qquad q=x-y.$$
\(x=(p+q)/2\) ve \(y=(p-q)/2\) olduğundan kafes noktası koşulu \(p\equiv q\pmod 2\) haline gelir; elmas koşulu da
$$|p|\le r,\qquad |q|\le r$$
şeklinde sadeleşir. Şimdi \(r/2 \lt s\le r\) olacak biçimde sabit bir \(p=s\) diyagonal seviyesi alalım. Bu seviyede uygun noktalar, \([-r,r]\) aralığındaki ve \(s\) ile aynı pariteye sahip bütün \(q\) değerleridir. \(s\) çiftse \(r+1\), tekse \(r\) tane vardır.
\(r\) sayısı 4'ün katı olduğundan \(s=r/2+1,\dots,r\) aralığında tam \(r/4\) tane çift seviye ve \(r/4\) tane tek seviye bulunur. Bu yüzden
$$N_C=\frac r4(r+1)+\frac r4 r=\frac{r(2r+1)}{4}.$$
Böylece ikinci kapalı form da elde edilir.
Doğrusal olmayan tek koşul
$$x^2+y^2-a(x+y) \lt 0$$
eşitsizliğidir. Kare tamamlarsak
$$\left(x-\frac a2\right)^2+\left(y-\frac a2\right)^2 \lt \frac{a^2}{2},$$
ve 4 ile çarpınca
$$ (2x-a)^2+(2y-a)^2 \lt 2a^2 $$
elde edilir. Yani \(B\), çapı \(OC\) olan çemberin içinde olmalıdır. Kod bunun için
$$u=2x-a,\qquad v=2y-a$$
dönüşümünü kullanır; böylece \(u\) ve \(v\) tam sayı olur ve ikisi de \(a\) ile aynı pariteye sahip olur. Sol taraf tam sayı olduğu için katı eşitsizlik
$$u^2+v^2\le 2a^2-1$$
biçiminde yazılabilir. Sonuç olarak \(N_B\), sabit bir parite desenine sahip kafes noktalarının bir çember içinde sayılmasıdır. Uygulama, uygun negatif olmayan \(u\) değerlerini 2'şer artırarak gezer, her sütun için çember içinde kalan en büyük aynı pariteli \(v\) değerini tutar ve bu üst sınırı yalnızca aşağı indirir. Üst sınır \(v\) ise \(-v\) ile \(v\) arasındaki aynı pariteli değer sayısı \(v+1\) olur; \(u=0\) için tek sütun, \(u\ne 0\) için ise \(\pm u\) simetrisi nedeniyle çift katkı vardır.
Bu durumda \(a=2\) olur. İlk iki parça
$$N_O=8^2+\frac 82=68,\qquad N_C=\frac{8(17)}{4}=34$$
şeklindedir. \(B\) köşesi için eşitsizlik
$$x^2+y^2-2(x+y)\lt 0\iff (x-1)^2+(y-1)^2\lt 2$$
haline gelir. Bu çemberin içinde kalan tam sayı noktalar
$$ (1,0),\ (0,1),\ (1,1),\ (2,1),\ (1,2) $$
olduğundan \(N_B=5\) bulunur. Bunlardan \((1,1)\) noktası \(y=x\) üzerinde olduğu için dejenere sayılacaktır. Birazdan açıklanan genel düzeltme ile toplam
$$68+34+5-7=100$$
olur; bu da uygulamaların küçük kontrol örneğiyle aynıdır.
\(-r/2\le t\le r/2\) aralığındaki bütün \(B=(t,t)\) noktaları \(O\) ve \(C\) ile doğrusal olduğundan geçerli üçgen oluşturmaz. Bunların ikisi, \(t=0\) ve \(t=a\), zaten sırasıyla \(O\) ve \(C\) noktalarıdır; ilgili iççarpımlar negatif değil sıfır olduğundan bu ikisi baştan beri sayılmamıştır.
Doğru üzerindeki diğer her nokta yukarıdaki üç bölgeden tam birine düşer:
$$t\lt 0 \Rightarrow N_O\text{ içinde},$$
$$0\lt t\lt a \Rightarrow N_B\text{ içinde},$$
$$t\gt a \Rightarrow N_C\text{ içinde}.$$
Bunların sayısı
$$\frac r2+\left(\frac r4-1\right)+\frac r4=r-1$$
olur. Son formül bu yüzden
$$N(r)=N_O+N_C+N_B-(r-1)$$
şeklindedir.
C++, Python ve Java uygulamaları önce \(a=r/4\) değerini hesaplar, ardından \(N_O=r^2+r/2\) ve \(N_C=r(2r+1)/4\) terimlerini doğrudan tamsayı aritmetiğiyle üretir. Bu iki parça için döngü gerekmez.
Döngü yalnızca \(N_B\) için kullanılır. Problem \(u^2+v^2\le 2a^2-1\) ve \(u\equiv v\equiv a\pmod 2\) koşuluna çevrilir. Bir tamsayı karekök işlemi başlangıçtaki \(v\) üst sınırını verir; sonra \(u\) 2'şer artarken, mevcut çift çemberin dışına çıkarsa \(v\) azaltılır. Uygun en büyük \(v\) değeri \(u\) büyüdükçe artamayacağı için arama iki boyutlu değil, tek yönlü monotone bir taramadır.
Her kabul edilen \(u\) için uygulama \(v+1\) adet aynı pariteli \(v\) değeri ekler; \(u=0\) değilse katkıyı ikiyle çarpar. Son adımda evrensel dejenere düzeltmesi olan \(r-1\) çıkarılır. C++ sürümü ayrıca küçük yarıçaplar üzerinde kontrol testleri içerir ve isterse \(u\) aralığını iş parçacıklarına bölebilir; Python ve Java sürümleri aynı matematiği seri biçimde uygular.
İki doğrusal bölge ve dejenere düzeltmesi \(O(1)\) maliyetlidir. Çember fazı yalnızca uygun \(u\) değerlerini dolaştığı için dış döngü \(O(a)\) adımdır; \(v\) işaretçisi de toplamda en fazla \(O(a)\) kez aşağı iner. Dolayısıyla toplam süre \(a=r/4\) için \(O(a)=O(r)\) olur.
Bellek kullanımı seri uygulamalarda \(O(1)\)'dir; çok iş parçacıklı C++ sürümünde de işçi başına ek bellek sabit kalır. Temel kazanç, çember içindeki her noktayı tek tek denemek yerine her uygun \(u\) sütununu en üst geçerli \(v\) bulununca tek hamlede saymaktır.
Sea \(r\) un múltiplo de 4 y definamos \(a=r/4\). Los vértices fijos son \(O=(0,0)\) y \(C=(a,a)\). El tercer vértice \(B=(x,y)\) recorre todos los puntos de la retícula dentro del diamante taxicab
$$|x|+|y|\le r.$$
Hay que contar cuántos triángulos no degenerados \(OBC\) son obtusos. La dificultad geométrica es que la región permitida está descrita con norma \(L_1\), mientras que el criterio de obtusidad usa producto escalar euclidiano. Por eso la solución separa los casos según el vértice obtuso y transforma el único caso no lineal en un conteo de puntos de retícula dentro de un círculo con una restricción de paridad.
Un triángulo es obtuso exactamente cuando uno de sus ángulos tiene producto punto negativo. Con \(B=(x,y)\) y \(C=(a,a)\), los tres tests son
$$\overrightarrow{OB}\cdot\overrightarrow{OC}=a(x+y),$$
$$\overrightarrow{CO}\cdot\overrightarrow{CB}=2a^2-a(x+y),$$
$$\overrightarrow{BO}\cdot\overrightarrow{BC}=x^2+y^2-a(x+y).$$
Por lo tanto, el ángulo obtuso aparece en
$$O \iff x+y \lt 0,$$
$$C \iff x+y \gt 2a=\frac r2,$$
$$B \iff x^2+y^2-a(x+y) \lt 0.$$
Estas tres regiones pueden contarse por separado, porque un triángulo no degenerado no puede tener dos ángulos obtusos. La única corrección global necesaria es quitar la recta colineal \(y=x\).
El diamante \( |x|+|y|\le r \) contiene en total
$$1+2r(r+1)=2r^2+2r+1$$
puntos de retícula. La línea divisoria entre \(x+y \lt 0\) y \(x+y \gt 0\) es \(x+y=0\), cuyos puntos son \((t,-t)\) con \(|t|\le r/2\); por tanto hay exactamente \(r+1\) puntos sobre esa línea.
Por simetría del diamante respecto de \(x+y=0\), la semirregión estricta \(x+y \lt 0\) contiene la mitad de los puntos restantes:
$$N_O=\frac{(2r^2+2r+1)-(r+1)}{2}=r^2+\frac r2.$$
Ese es el primer término cerrado usado por las implementaciones.
Para la desigualdad \(x+y \gt r/2\) conviene usar coordenadas diagonales
$$p=x+y,\qquad q=x-y.$$
Como \(x=(p+q)/2\) e \(y=(p-q)/2\), la condición de integralidad se vuelve \(p\equiv q\pmod 2\), mientras que el diamante queda descrito por
$$|p|\le r,\qquad |q|\le r.$$
Fijemos ahora un nivel diagonal \(p=s\) con \(r/2 \lt s\le r\). En ese nivel, los puntos válidos son exactamente los valores enteros \(q\in[-r,r]\) que tienen la misma paridad que \(s\). Si \(s\) es par, hay \(r+1\) opciones; si es impar, hay \(r\).
Como \(r\) es múltiplo de 4, en el intervalo \(s=r/2+1,\dots,r\) aparecen exactamente \(r/4\) niveles pares y \(r/4\) niveles impares. Entonces
$$N_C=\frac r4(r+1)+\frac r4 r=\frac{r(2r+1)}{4}.$$
Así se obtiene el segundo término cerrado.
La tercera condición, la única no lineal, es
$$x^2+y^2-a(x+y) \lt 0.$$
Completando cuadrados se obtiene
$$\left(x-\frac a2\right)^2+\left(y-\frac a2\right)^2 \lt \frac{a^2}{2},$$
y multiplicando por 4,
$$ (2x-a)^2+(2y-a)^2 \lt 2a^2. $$
Geométricamente, eso significa que \(B\) debe estar estrictamente dentro del círculo cuyo diámetro es \(OC\). Las implementaciones usan las coordenadas escaladas
$$u=2x-a,\qquad v=2y-a,$$
porque así \(u\) y \(v\) son enteros y ambos tienen la misma paridad que \(a\). Como el lado izquierdo es entero, la desigualdad estricta equivale a
$$u^2+v^2\le 2a^2-1.$$
Por tanto, \(N_B\) es un conteo de puntos de retícula dentro de un círculo con un patrón de paridad fijo. El código recorre los valores no negativos admisibles de \(u\) en pasos de 2, mantiene el mayor \(v\) con la misma paridad que aún satisface la desigualdad del círculo y solo mueve ese puntero hacia abajo. Si el máximo actual es \(v\), entonces entre \(-v\) y \(v\) hay exactamente \(v+1\) valores con la paridad correcta; además, la contribución se cuenta una vez cuando \(u=0\) y dos veces cuando \(u\ne 0\) por la simetría \(u\leftrightarrow -u\).
Aquí \(a=2\). Los dos términos cerrados valen
$$N_O=8^2+\frac 82=68,\qquad N_C=\frac{8(17)}{4}=34.$$
La condición del ángulo en \(B\) se convierte en
$$x^2+y^2-2(x+y)\lt 0\iff (x-1)^2+(y-1)^2\lt 2.$$
Los puntos enteros estrictamente dentro de ese círculo son
$$ (1,0),\ (0,1),\ (1,1),\ (2,1),\ (1,2), $$
así que \(N_B=5\). Uno de ellos, \((1,1)\), está sobre \(y=x\) y por tanto es degenerado. Después de aplicar la corrección global del apartado siguiente, el total queda
$$68+34+5-7=100,$$
que coincide con el pequeño caso de prueba usado por las implementaciones.
Todos los puntos \(B=(t,t)\) con \(-r/2\le t\le r/2\) son colineales con \(O\) y \(C\), así que no forman triángulos válidos. Dos de esos puntos, \(t=0\) y \(t=a\), son precisamente \(O\) y \(C\), y nunca fueron contados porque en ellos los productos punto relevantes valen cero, no un número negativo.
Cada uno de los demás puntos sobre \(y=x\) apareció exactamente una vez en los tres conteos anteriores:
$$t\lt 0 \Rightarrow \text{aparece en }N_O,$$
$$0\lt t\lt a \Rightarrow \text{aparece en }N_B,$$
$$t\gt a \Rightarrow \text{aparece en }N_C.$$
Su número total es
$$\frac r2+\left(\frac r4-1\right)+\frac r4=r-1.$$
Por eso la fórmula final es
$$N(r)=N_O+N_C+N_B-(r-1).$$
Las implementaciones en C++, Python y Java comienzan calculando \(a=r/4\) y luego evalúan directamente las dos contribuciones cerradas \(N_O=r^2+r/2\) y \(N_C=r(2r+1)/4\) con aritmética entera. En esas partes no hace falta iterar por los puntos del diamante.
La parte iterativa es solo \(N_B\). El problema se reescribe como \(u^2+v^2\le 2a^2-1\) bajo la condición de paridad \(u\equiv v\equiv a\pmod 2\). Una raíz cuadrada entera fija el valor inicial de \(v\); después \(u\) avanza en pasos de 2 y \(v\) se reduce únicamente cuando el par actual cae fuera del círculo. Como el máximo \(v\) factible nunca aumenta al crecer \(u\), el recorrido es monótono y lineal.
Para cada \(u\) aceptado, la implementación suma \(v+1\) valores admisibles de \(v\) y duplica la contribución salvo cuando \(u=0\). Al final resta la corrección degenerada universal \(r-1\). La versión en C++ además incluye comprobaciones con radios pequeños y puede repartir el intervalo de \(u\) entre varios hilos; las versiones en Python y Java aplican la misma lógica de forma secuencial.
Los dos conteos por semiplanos y la corrección degenerada cuestan \(O(1)\). La fase circular recorre solo los valores admisibles de \(u\), así que el bucle exterior tiene \(O(a)\) iteraciones, y el puntero de \(v\) desciende como mucho \(O(a)\) veces en total. En consecuencia, el tiempo total es \(O(a)=O(r)\), con \(a=r/4\).
La memoria usada es \(O(1)\) en las implementaciones secuenciales y sigue siendo \(O(1)\) extra por trabajador en la variante paralela de C++. La optimización esencial consiste en no probar cada punto del círculo por separado, sino contar de golpe cada columna admisible de \(u\) una vez conocido su mayor \(v\) válido.
设 \(r\) 是 4 的倍数，并记 \(a=r/4\)。固定点为 \(O=(0,0)\) 与 \(C=(a,a)\)。第三个顶点 \(B=(x,y)\) 在如下 taxicab 菱形中的所有整点上取值：
$$|x|+|y|\le r.$$
目标是统计有多少个非退化三角形 \(OBC\) 是钝角三角形。这个问题的几何结构有一个明显的“错位”：允许区域由 \(L_1\) 范数给出，而钝角判定却由欧氏几何中的点积给出。代码的关键做法，是先按“钝角出现在哪个顶点”把问题拆开，再把唯一的非线性部分改写成一个带奇偶约束的圆内整点计数问题。
三角形是钝角三角形，当且仅当某个顶点对应的点积为负。令 \(B=(x,y)\)、\(C=(a,a)\)，则三个顶点对应的判定式分别是
$$\overrightarrow{OB}\cdot\overrightarrow{OC}=a(x+y),$$
$$\overrightarrow{CO}\cdot\overrightarrow{CB}=2a^2-a(x+y),$$
$$\overrightarrow{BO}\cdot\overrightarrow{BC}=x^2+y^2-a(x+y).$$
于是钝角出现在
$$O \iff x+y \lt 0,$$
$$C \iff x+y \gt 2a=\frac r2,$$
$$B \iff x^2+y^2-a(x+y) \lt 0.$$
非退化三角形不可能同时有两个钝角，所以这三部分可以分开计数。唯一需要统一修正的，是三点共线的情形 \(y=x\)。
菱形区域 \( |x|+|y|\le r \) 的整点总数为
$$1+2r(r+1)=2r^2+2r+1.$$
把平面分成 \(x+y \lt 0\) 与 \(x+y \gt 0\) 两部分的分界线是 \(x+y=0\)。落在这条线上的整点形如 \((t,-t)\)，并满足 \(|t|\le r/2\)，因此共有 \(r+1\) 个。
由于整个菱形关于直线 \(x+y=0\) 对称，所以除去这条分界线后，剩余整点恰好一半落在 \(x+y \lt 0\) 这一侧：
$$N_O=\frac{(2r^2+2r+1)-(r+1)}{2}=r^2+\frac r2.$$
这就是程序直接使用的第一个闭式项。
对不等式 \(x+y \gt r/2\)，最方便的做法是改用对角坐标
$$p=x+y,\qquad q=x-y.$$
因为 \(x=(p+q)/2\)、\(y=(p-q)/2\)，所以整点条件等价于 \(p\equiv q\pmod 2\)。而菱形条件则变成
$$|p|\le r,\qquad |q|\le r.$$
现在固定一条对角层 \(p=s\)，其中 \(r/2 \lt s\le r\)。在这一层上，所有可行点正好对应于区间 \([-r,r]\) 中与 \(s\) 同奇偶性的整数 \(q\)。若 \(s\) 为偶数，这样的 \(q\) 有 \(r+1\) 个；若 \(s\) 为奇数，则有 \(r\) 个。
由于 \(r\) 是 4 的倍数，所以从 \(s=r/2+1\) 到 \(s=r\) 的这些层里，恰好有 \(r/4\) 个偶数层和 \(r/4\) 个奇数层。因此
$$N_C=\frac r4(r+1)+\frac r4 r=\frac{r(2r+1)}{4}.$$
这给出了第二个闭式贡献。
第三个条件也是唯一的非线性条件：
$$x^2+y^2-a(x+y) \lt 0.$$
配方后可得
$$\left(x-\frac a2\right)^2+\left(y-\frac a2\right)^2 \lt \frac{a^2}{2},$$
再乘以 4，化为
$$ (2x-a)^2+(2y-a)^2 \lt 2a^2. $$
几何上，这说明 \(B\) 必须严格位于以 \(OC\) 为直径的圆内部。实现中进一步引入缩放坐标
$$u=2x-a,\qquad v=2y-a,$$
这样 \(u\) 与 \(v\) 都是整数，并且它们都与 \(a\) 同奇偶。因为左边一定是整数，严格不等式可以等价写成
$$u^2+v^2\le 2a^2-1.$$
于是 \(N_B\) 变成“固定奇偶模式下，圆内有多少整点”的问题。代码只扫描非负且满足奇偶性的 \(u\)，步长为 2；对每个 \(u\)，维护当前仍在圆内的最大同奇偶 \(v\)。随着 \(u\) 增大，允许的最大 \(v\) 只会下降，不会回升，所以整个过程是单调扫描，而不是二维暴力枚举。若当前上界为 \(v\)，则从 \(-v\) 到 \(v\) 的同奇偶整数共有 \(v+1\) 个；再利用 \(u\leftrightarrow -u\) 的对称性，在 \(u\ne 0\) 时把该列贡献乘 2。
此时 \(a=2\)。前两个闭式项为
$$N_O=8^2+\frac 82=68,\qquad N_C=\frac{8(17)}{4}=34.$$
而 \(B\) 处钝角条件变成
$$x^2+y^2-2(x+y)\lt 0\iff (x-1)^2+(y-1)^2\lt 2.$$
严格落在这个圆内的整点共有五个：
$$ (1,0),\ (0,1),\ (1,1),\ (2,1),\ (1,2). $$
因此 \(N_B=5\)。其中 \((1,1)\) 在直线 \(y=x\) 上，是退化情形，后面要统一扣掉。最终总数为
$$68+34+5-7=100,$$
这与实现里使用的小规模检验值完全一致。
所有满足 \(-r/2\le t\le r/2\) 的点 \(B=(t,t)\)，都与 \(O\) 和 \(C\) 共线，因此不能形成有效三角形。其中 \(t=0\) 与 \(t=a\) 分别对应 \(O\) 和 \(C\) 本身，它们从一开始就没有被计入，因为相关点积在那里等于 0 而不是负数。
直线 \(y=x\) 上其余的点，各自恰好被前三部分中的一项计算到一次：
$$t\lt 0 \Rightarrow \text{计入 }N_O,$$
$$0\lt t\lt a \Rightarrow \text{计入 }N_B,$$
$$t\gt a \Rightarrow \text{计入 }N_C.$$
这些点的总数为
$$\frac r2+\left(\frac r4-1\right)+\frac r4=r-1.$$
所以最终公式就是
$$N(r)=N_O+N_C+N_B-(r-1).$$
C++、Python 和 Java 实现都会先计算 \(a=r/4\)，然后直接用整数公式得到 \(N_O=r^2+r/2\) 与 \(N_C=r(2r+1)/4\)。这两部分完全不需要遍历候选点。
唯一需要扫描的是 \(N_B\)。实现先把问题改写成 \(u^2+v^2\le 2a^2-1\)，并强制 \(u\equiv v\equiv a\pmod 2\)。随后通过整数平方根得到初始的 \(v\) 上界，让 \(u\) 以步长 2 前进；如果当前 \((u,v)\) 超出圆，就不断减小 \(v\)。由于可行的最大 \(v\) 随 \(u\) 增大只能不变或下降，因此这是一次单调扫过，而不是回溯搜索。
对每个合法的 \(u\)，实现累加 \(v+1\) 个同奇偶的 \(v\) 值；若 \(u\ne 0\)，再乘 2 来覆盖 \(\pm u\) 两列。最后统一减去退化修正 \(r-1\)。C++ 版本还包含小半径的检查，并且可以把 \(u\) 的区间拆给多个线程；Python 与 Java 版本则按相同数学逻辑串行执行。
两个线性区域的计数以及最终的退化修正都是 \(O(1)\)。圆内计数阶段只访问满足奇偶条件的 \(u\)，因此外层循环是 \(O(a)\)；同时 \(v\) 指针在整个过程中最多下降 \(O(a)\) 次。故总时间复杂度为 \(O(a)=O(r)\)，其中 \(a=r/4\)。
空间复杂度在串行实现中为 \(O(1)\)，在线程版中也只是每个工作线程额外 \(O(1)\)。真正的效率来自“按列计数”而不是“逐点试探”：一旦某个 \(u\) 的最大合法 \(v\) 被找到，该列就能一次性计入答案。
Пусть \(r\) кратно 4 и \(a=r/4\). Фиксированные вершины равны \(O=(0,0)\) и \(C=(a,a)\). Третья вершина \(B=(x,y)\) пробегает все целочисленные точки внутри ромба taxicab
$$|x|+|y|\le r.$$
Нужно подсчитать, сколько невырожденных треугольников \(OBC\) являются тупоугольными. Трудность в том, что область допустимых точек задается нормой \(L_1\), а проверка тупого угла основана на евклидовом скалярном произведении. Поэтому решение сначала разбивает задачу по тому, в какой вершине возникает тупой угол, а затем переводит единственный нелинейный случай в задачу о подсчете решеточных точек внутри круга с ограничением на четность.
Треугольник является тупоугольным тогда и только тогда, когда для одного из его углов соответствующее скалярное произведение отрицательно. При \(B=(x,y)\) и \(C=(a,a)\) получаем
$$\overrightarrow{OB}\cdot\overrightarrow{OC}=a(x+y),$$
$$\overrightarrow{CO}\cdot\overrightarrow{CB}=2a^2-a(x+y),$$
$$\overrightarrow{BO}\cdot\overrightarrow{BC}=x^2+y^2-a(x+y).$$
Следовательно, тупой угол находится в
$$O \iff x+y \lt 0,$$
$$C \iff x+y \gt 2a=\frac r2,$$
$$B \iff x^2+y^2-a(x+y) \lt 0.$$
Эти три области можно считать независимо, потому что невырожденный треугольник не может иметь два тупых угла. Общая поправка понадобится только для коллинеарной прямой \(y=x\).
Ромб \( |x|+|y|\le r \) содержит всего
$$1+2r(r+1)=2r^2+2r+1$$
решеточных точек. Разделяющая прямая между \(x+y \lt 0\) и \(x+y \gt 0\) имеет вид \(x+y=0\). Ее точки записываются как \((t,-t)\) при \(|t|\le r/2\), то есть всего их \(r+1\).
Из симметрии ромба относительно этой диагонали следует, что строгая полуплоскость \(x+y \lt 0\) содержит половину всех оставшихся точек:
$$N_O=\frac{(2r^2+2r+1)-(r+1)}{2}=r^2+\frac r2.$$
Это первый замкнутый вклад, используемый в реализациях.
Для неравенства \(x+y \gt r/2\) удобно перейти к диагональным координатам
$$p=x+y,\qquad q=x-y.$$
Так как \(x=(p+q)/2\) и \(y=(p-q)/2\), условие целочисленности эквивалентно \(p\equiv q\pmod 2\), а ромб описывается просто как
$$|p|\le r,\qquad |q|\le r.$$
Зафиксируем теперь уровень \(p=s\), где \(r/2 \lt s\le r\). На этом уровне допустимы ровно те целые значения \(q\in[-r,r]\), которые имеют ту же четность, что и \(s\). Если \(s\) четно, таких значений \(r+1\); если нечетно, то \(r\).
Поскольку \(r\) кратно 4, среди уровней \(s=r/2+1,\dots,r\) имеется ровно \(r/4\) четных и \(r/4\) нечетных значений. Поэтому
$$N_C=\frac r4(r+1)+\frac r4 r=\frac{r(2r+1)}{4}.$$
Так получается второй замкнутый член.
Третье условие, единственное нелинейное, имеет вид
$$x^2+y^2-a(x+y) \lt 0.$$
Дополняя до квадратов, получаем
$$\left(x-\frac a2\right)^2+\left(y-\frac a2\right)^2 \lt \frac{a^2}{2},$$
а после умножения на 4
$$ (2x-a)^2+(2y-a)^2 \lt 2a^2. $$
Геометрически это означает, что точка \(B\) должна лежать строго внутри круга с диаметром \(OC\). Реализации вводят масштабированные координаты
$$u=2x-a,\qquad v=2y-a,$$
чтобы работать только с целыми числами. При этом и \(u\), и \(v\) имеют ту же четность, что и \(a\). Так как левая часть целая, строгое неравенство эквивалентно
$$u^2+v^2\le 2a^2-1.$$
Значит, \(N_B\) сводится к подсчету решеточных точек внутри круга при фиксированной четности координат. Код перебирает допустимые неотрицательные значения \(u\) с шагом 2, поддерживает наибольшее допустимое значение \(v\) той же четности и сдвигает этот указатель только вниз. Если текущий максимум равен \(v\), то среди чисел от \(-v\) до \(v\) ровно \(v+1\) значений имеют нужную четность; при \(u\ne 0\) вклад затем удваивается за счет симметрии \(u\leftrightarrow -u\).
Здесь \(a=2\). Два замкнутых вклада равны
$$N_O=8^2+\frac 82=68,\qquad N_C=\frac{8(17)}{4}=34.$$
Условие тупого угла в вершине \(B\) превращается в
$$x^2+y^2-2(x+y)\lt 0\iff (x-1)^2+(y-1)^2\lt 2.$$
Строго внутри этого круга лежат пять целочисленных точек
$$ (1,0),\ (0,1),\ (1,1),\ (2,1),\ (1,2). $$
Следовательно, \(N_B=5\). Точка \((1,1)\) лежит на прямой \(y=x\), поэтому она вырожденная и позже будет вычтена общей поправкой. Итоговое значение равно
$$68+34+5-7=100,$$
что совпадает с малой контрольной проверкой в реализациях.
Все точки вида \(B=(t,t)\) при \(-r/2\le t\le r/2\) коллинеарны с \(O\) и \(C\), поэтому допустимого треугольника не образуют. Две из них, \(t=0\) и \(t=a\), это сами \(O\) и \(C\); они и так не были посчитаны, потому что соответствующие скалярные произведения там равны нулю, а не отрицательны.
Каждая из остальных точек на прямой \(y=x\) была учтена ровно один раз:
$$t\lt 0 \Rightarrow \text{входит в }N_O,$$
$$0\lt t\lt a \Rightarrow \text{входит в }N_B,$$
$$t\gt a \Rightarrow \text{входит в }N_C.$$
Их количество равно
$$\frac r2+\left(\frac r4-1\right)+\frac r4=r-1.$$
Отсюда окончательная формула
$$N(r)=N_O+N_C+N_B-(r-1).$$
Реализации на C++, Python и Java сначала вычисляют \(a=r/4\), после чего напрямую получают два замкнутых вклада \(N_O=r^2+r/2\) и \(N_C=r(2r+1)/4\) в целой арифметике. Для этих частей не требуется проход по точкам ромба.
Итеративной остается только величина \(N_B\). Программа переписывает задачу как \(u^2+v^2\le 2a^2-1\) с условием \(u\equiv v\equiv a\pmod 2\). Начальное значение \(v\) берется через целочисленный квадратный корень; затем \(u\) увеличивается с шагом 2, а \(v\) уменьшается лишь тогда, когда текущая пара выходит за пределы круга. Поскольку максимально допустимый \(v\) при росте \(u\) не возрастает, получается монотонный линейный sweep.
Для каждого допустимого \(u\) реализация добавляет \(v+1\) значений \(v\) нужной четности и удваивает вклад, если \(u\ne 0\). После этого вычитается универсальная поправка \(r-1\). В версии на C++ есть также проверки на малых радиусах и возможность разбить диапазон \(u\) между потоками; Python и Java выполняют те же вычисления последовательно.
Два линейных подсчета и финальная поправка на вырожденность выполняются за \(O(1)\). Круговая фаза рассматривает только допустимые значения \(u\), поэтому внешний цикл имеет \(O(a)\) шагов, а указатель \(v\) в сумме опускается не более чем на \(O(a)\). Следовательно, полное время работы равно \(O(a)=O(r)\), где \(a=r/4\).
Память составляет \(O(1)\) в последовательных версиях и остается \(O(1)\) дополнительно на поток в параллельной версии C++. Ключевая идея в том, что решетка внутри круга не просматривается по точкам: после нахождения верхнего допустимого \(v\) вся колонка по фиксированному \(u\) учитывается сразу.
ليكن \(r\) من مضاعفات 4، ولنكتب \(a=r/4\). النقطتان الثابتتان هما \(O=(0,0)\) و\(C=(a,a)\)، أمّا النقطة الثالثة \(B=(x,y)\) فتجول على جميع نقاط الشبكة داخل المعين
$$|x|+|y|\le r.$$
المطلوب هو عدّ عدد المثلثات غير المتدهورة \(OBC\) التي تكون منفرجة الزاوية. الصعوبة هنا أن مجال الاختيار موصوف بمعيار \(L_1\)، بينما اختبار الانفراج نفسه يعتمد على الهندسة الإقليدية والضرب النقطي. لذلك يفصل الحل العدّ بحسب الرأس الذي تقع عنده الزاوية المنفرجة، ثم يحول الحالة غير الخطية الوحيدة إلى مسألة عدّ نقاط شبكية داخل دائرة مع قيد على الفردية والزوجية.
يكون المثلث منفرجًا إذا وفقط إذا كان الضرب النقطي الموافق لأحد زواياه سالبًا. مع \(B=(x,y)\) و\(C=(a,a)\) نحصل على
$$\overrightarrow{OB}\cdot\overrightarrow{OC}=a(x+y),$$
$$\overrightarrow{CO}\cdot\overrightarrow{CB}=2a^2-a(x+y),$$
$$\overrightarrow{BO}\cdot\overrightarrow{BC}=x^2+y^2-a(x+y).$$
إذًا تكون الزاوية المنفرجة عند
$$O \iff x+y \lt 0,$$
$$C \iff x+y \gt 2a=\frac r2,$$
$$B \iff x^2+y^2-a(x+y) \lt 0.$$
يمكن عدّ هذه المناطق الثلاث كلٌّ على حدة، لأن المثلث غير المتدهور لا يمكن أن يملك زاويتين منفرجتين. التصحيح الوحيد المشترك بين هذه الأجزاء هو حذف الحالات الخطية على المستقيم \(y=x\).
يحتوي المعين \( |x|+|y|\le r \) على
$$1+2r(r+1)=2r^2+2r+1$$
نقطة شبكية في المجموع. أمّا المستقيم الفاصل بين \(x+y \lt 0\) و\(x+y \gt 0\) فهو \(x+y=0\)، ونقاطه من الشكل \((t,-t)\) مع \(|t|\le r/2\)، أي وعددها بالضبط \(r+1\).
وبسبب تناظر المعين حول هذا المستقيم، فإن نصف النقاط الباقية بعد حذف المستقيم يقع في نصف المستوى الصارم \(x+y \lt 0\):
$$N_O=\frac{(2r^2+2r+1)-(r+1)}{2}=r^2+\frac r2.$$
وهذا هو الحد المغلق الأول الذي تستخدمه التطبيقات.
بالنسبة إلى الشرط \(x+y \gt r/2\)، يكون الانتقال إلى الإحداثيات القطرية أكثر وضوحًا:
$$p=x+y,\qquad q=x-y.$$
ولأن \(x=(p+q)/2\) و\(y=(p-q)/2\)، فإن شرط كون \(x,y\) عددين صحيحين يصبح \(p\equiv q\pmod 2\)، بينما يتحول شرط المعين إلى
$$|p|\le r,\qquad |q|\le r.$$
لنثبت الآن مستوى قطريًا \(p=s\) حيث \(r/2 \lt s\le r\). عند هذا المستوى تكون النقاط المسموح بها هي جميع القيم الصحيحة \(q\in[-r,r]\) التي لها نفس فردية أو زوجية \(s\). إذا كان \(s\) زوجيًا فعددها \(r+1\)، وإذا كان فرديًا فعددها \(r\).
وبما أن \(r\) من مضاعفات 4، فإن المستويات \(s=r/2+1,\dots,r\) تحتوي بالضبط على \(r/4\) مستويات زوجية و\(r/4\) مستويات فردية. لذلك
$$N_C=\frac r4(r+1)+\frac r4 r=\frac{r(2r+1)}{4}.$$
وهكذا نحصل على الحد المغلق الثاني.
الشرط الثالث، وهو الوحيد غير الخطي، هو
$$x^2+y^2-a(x+y) \lt 0.$$
وبإكمال المربع نحصل على
$$\left(x-\frac a2\right)^2+\left(y-\frac a2\right)^2 \lt \frac{a^2}{2},$$
وبعد الضرب في 4 يصبح
$$ (2x-a)^2+(2y-a)^2 \lt 2a^2. $$
هذا يعني هندسيًا أن \(B\) يجب أن تقع strictly داخل الدائرة التي قطرها \(OC\). تستعمل التطبيقات الإحداثيين المكبّرين
$$u=2x-a,\qquad v=2y-a,$$
لأنهما عددان صحيحان، وكلاهما يملك نفس فردية أو زوجية \(a\). وبما أن الطرف الأيسر عدد صحيح، فإن عدم المساواة الصارمة تكافئ
$$u^2+v^2\le 2a^2-1.$$
إذن \(N_B\) هو عدد نقاط الشبكة داخل دائرة مع نمط parity ثابت. يسير الكود على قيم \(u\) غير السالبة المسموح بها بخطوة 2، ويحافظ على أكبر قيمة \(v\) لها نفس parity وما تزال تحقق شرط الدائرة، ولا يحرّك هذا الحد العلوي إلا إلى الأسفل. فإذا كانت القيمة القصوى الحالية هي \(v\)، فإن عدد القيم الموقعة ذات parity نفسه بين \(-v\) و\(v\) يساوي \(v+1\). كما أن المساهمة تتضاعف عندما \(u\ne 0\) بسبب التناظر بين \(u\) و\(-u\).
في هذه الحالة \(a=2\). الجزآن المغلقان يساويان
$$N_O=8^2+\frac 82=68,\qquad N_C=\frac{8(17)}{4}=34.$$
أما شرط الزاوية المنفرجة عند \(B\) فيصبح
$$x^2+y^2-2(x+y)\lt 0\iff (x-1)^2+(y-1)^2\lt 2.$$
والنقاط الصحيحة الواقعة strictly داخل هذه الدائرة هي
$$ (1,0),\ (0,1),\ (1,1),\ (2,1),\ (1,2). $$
ومن ثم \(N_B=5\). لكن النقطة \((1,1)\) تقع على المستقيم \(y=x\)، ولذلك فهي حالة متدهورة وستُطرح لاحقًا. بعد تطبيق التصحيح العام نحصل على
$$68+34+5-7=100,$$
وهو نفس المثال الصغير الذي تتحقق منه التطبيقات.
كل نقطة من الشكل \(B=(t,t)\) مع \(-r/2\le t\le r/2\) تقع على استقامة واحدة مع \(O\) و\(C\)، ولذلك لا تنتج مثلثًا صالحًا. نقطتان من هذه المجموعة، وهما \(t=0\) و\(t=a\)، تمثلان \(O\) و\(C\) نفسيهما، ولم تكونا معدودتين أصلًا لأن الضربات النقطية المعنية عندهما تساوي صفرًا لا عددًا سالبًا.
أما بقية النقاط على \(y=x\) فقد عُدَّت مرة واحدة بالضبط ضمن الحالات الثلاث السابقة:
إذا كان \(t\lt 0\) فإن النقطة تُعد ضمن \(N_O\).
إذا كان \(0\lt t\lt a\) فإنها تُعد ضمن \(N_B\).
إذا كان \(t\gt a\) فإنها تُعد ضمن \(N_C\).
وعددها هو
$$\frac r2+\left(\frac r4-1\right)+\frac r4=r-1.$$
ولهذا تكون الصيغة النهائية
$$N(r)=N_O+N_C+N_B-(r-1).$$
تبدأ تطبيقات C++ وPython وJava بحساب \(a=r/4\)، ثم تحسب مباشرة الحدين المغلقين \(N_O=r^2+r/2\) و\(N_C=r(2r+1)/4\) باستخدام حساب صحيح بالكامل. لا تحتاج هاتان المرحلتان إلى أي فحص نقطة بنقطة.
الجزء التكراري الوحيد هو \(N_B\). تعيد التطبيقات كتابة المسألة على صورة \(u^2+v^2\le 2a^2-1\) مع الشرط \(u\equiv v\equiv a\pmod 2\). ثم تُستخدم الجذرية الصحيحة لتحديد قيمة \(v\) الابتدائية، ويُزاد \(u\) بخطوة 2، بينما يُنقَص \(v\) فقط إذا خرج الزوج الحالي من الدائرة. وبما أن أكبر \(v\) صالح لا يمكن أن يزداد مع ازدياد \(u\)، فإن العملية كلها sweep أحادي الاتجاه.
لكل قيمة \(u\) مقبولة، تضيف الخوارزمية \(v+1\) قيمة صالحة لـ \(v\)، ثم تضاعف المساهمة إلا عند \(u=0\). وفي النهاية تُطرح قيمة التدهور العامة \(r-1\). نسخة C++ تحتوي أيضًا على اختبارات صغيرة ويمكنها تقسيم مجال \(u\) على عدة خيوط تنفيذ، بينما تطبق نسختا Python وJava نفس الرياضيات بصورة تسلسلية.
حساب منطقتي أنصاف المستويات والتصحيح النهائي للتدهور يتم في \(O(1)\). أمّا مرحلة الدائرة فتمر فقط على قيم \(u\) المسموح بها، ولذلك فعدد دورات الحلقة الخارجية هو \(O(a)\)، كما أن مؤشّر \(v\) يهبط إجمالًا بحد أقصى \(O(a)\) مرة. وعليه فإن الزمن الكلي هو \(O(a)=O(r)\) حيث \(a=r/4\).
استهلاك الذاكرة هو \(O(1)\) في التطبيقات التسلسلية، ويظل \(O(1)\) إضافيًا لكل عامل في النسخة متعددة الخيوط في C++. الفكرة الأساسية هنا هي عدم اختبار كل نقطة داخل الدائرة بشكل منفصل، بل عدّ كل عمود مسموح من قيم \(u\) دفعة واحدة بعد معرفة أعلى \(v\) صالح فيه.