We search for triangles with integer vertices \(A,B,C\in\mathbb{Z}^2\) such that all three points lie on the same circle centered at the origin and the centroid is fixed by
$$A+B+C=(5,0).$$
For every such triangle whose perimeter does not exceed the given limit, we add its perimeter to the total. The solver prints the final sum rounded to four decimal places.
Because the centroid is \((5/3,0)\), the vertex sum is the integer vector
$$H=(5,0).$$
If we choose one vertex \(C=(c_x,c_y)\), then the remaining two vertices satisfy
$$A+B=H-C=(5-c_x,-c_y).$$
The code calls this vector \(S\). Once \(C\) is fixed, the whole problem becomes: find integer pairs \(A,B\) with sum \(S\), equal distance from the origin, and correct perimeter.
Write
$$A=\frac{S+U}{2},\qquad B=\frac{S-U}{2},\qquad U:=A-B.$$
Then \(A\) and \(B\) have equal radius if and only if
$$|A|^2=|B|^2 \iff U\perp S.$$
Moreover, if the common radius is \(R\), then
$$|U|^2=4R^2-|S|^2,$$
because
$$4|A|^2=|S+U|^2=|S|^2+|U|^2,$$
and the same expression holds for \(B\). This is the central identity used by the code.
Since \(S=(s_x,s_y)\) is integral, every integer vector orthogonal to \(S\) lies on a one-dimensional lattice. Let
$$g=\gcd(|s_x|,|s_y|),\qquad P=\left(-\frac{s_y}{g},\frac{s_x}{g}\right).$$
Then \(P\) is the primitive integer normal vector to \(S\), and every integer orthogonal vector is
$$U=tP,\qquad t\in\mathbb{Z}.$$
Substituting this into the radius identity gives
$$t^2=\frac{(4R^2-|S|^2)g^2}{|S|^2}.$$
The solver checks exactly this quantity: it must be an integer square before \(A\) and \(B\) are even constructed.
Once \(U\) is known, the coordinates of \(A\) and \(B\) are obtained from \((S\pm U)/2\). Therefore each coordinate must have the correct parity; otherwise the pair is discarded immediately.
The code then rejects degenerate triangles by checking that the doubled area, computed by a cross product, is nonzero.
To avoid counting the same triangle multiple times, the code keeps only a canonical representative: the chosen vertex \(C\) must be lexicographically no larger than \(A\) and \(B\). This removes the six permutations of the same unlabeled triangle, while the fixed sign choice for the primitive normal vector removes the \(A\leftrightarrow B\) swap.
The code does not scan all possible radii blindly. It first derives an upper bound on the circumradius from the perimeter cap.
Using
$$AB^2=4R^2-|A+B|^2=4R^2-|H-C|^2,$$
and the triangle inequality \(|H-C|\le |H|+|C|=5+R\), we get
$$AB^2\ge 4R^2-(R+5)^2=3R^2-10R-25.$$
The same lower bound applies symmetrically to the three sides, so
$$P\ge 3\sqrt{3R^2-10R-25}.$$
Solving this inequality for \(R\) gives the radius cutoff used in the program. After that, the solver only scans integer points \(C=(c_x,c_y)\) with \(|C|\le R_{\max}\), and because \(C\) is the lexicographically smallest vertex, its \(x\)-coordinate must satisfy \(c_x\le 1\). That is why the outer scan stops at \(x=1\).
The implementation splits the \(c_x\)-range into chunks and distributes them across threads. Each thread keeps a local perimeter sum and triangle count, and the partial sums are merged at the end.
Geometric tests that need exactness use integer arithmetic and the integer square root helper. The final perimeter is computed with long double, then rounded to four decimals. The checkpoints in the code verify both a sample perimeter value and that the multi-threaded and single-threaded runs agree.
The checkpoints are concrete: the code requires round4(solve(50, 1)) = 291.0089, and it also checks that solve(300, 1) matches a multi-threaded run. One checkpoint validates the geometric pipeline numerically, and the other validates that the thread split does not change the result.
Take the valid triangle
$$C=(-4,-3),\qquad A=(4,3),\qquad B=(5,0).$$
All three vertices satisfy
$$|A|^2=|B|^2=|C|^2=25,$$
and also
$$A+B+C=(4+5-4,\ 3+0-3)=(5,0).$$
For this choice of \(C\), we get
$$S=H-C=(9,3),\qquad g=\gcd(9,3)=3,\qquad P=(-1,3).$$
The radius identity gives
$$t^2=\frac{(4\cdot 25-90)\cdot 3^2}{90}=1,$$
so \(t=1\) and therefore
$$U=tP=(-1,3).$$
Reconstructing the pair yields
$$A=\frac{S+U}{2}=(4,3),\qquad B=\frac{S-U}{2}=(5,0).$$
This is exactly what the code does for every admissible \(C\): derive \(S\), test whether the induced \(t^2\) is a perfect square, then rebuild \(A\) and \(B\) algebraically instead of enumerating all vertex triples.
The program accepts --perimeter, --threads, and --skip-checkpoints. The function solve first converts the perimeter limit into a radius bound \(R_{\max}\). It then scans integer points \(C=(c_x,c_y)\) inside that circle. For each \(C\), it forms
$$S=(5-c_x,-c_y),\qquad r^2=|C|^2.$$
After that it computes the primitive orthogonal vector \(P\), checks that the derived \(t^2\) is a perfect square, verifies parity, reconstructs \(A\) and \(B\), rejects degenerate or non-canonical triangles, and finally filters by the exact perimeter bound.
The helper isqrt_i64 is used both for radius estimates and square tests. The helper lex_leq implements the canonical ordering. The checkpoint routine compares the single-threaded and multi-threaded results and also checks the stored sample sum for perimeter \(50\).
The dominant work is the scan over candidate vertices \(C\) in the bounded disk. For each candidate, the solver performs only constant-time arithmetic, gcd, square-root, and geometry checks. Because the scan is restricted to \(c_x\le 1\) and \(|C|\le R_{\max}\), the search space is much smaller than all triples of vertices.
Time grows roughly quadratically with the radius bound, and the multi-threaded split reduces wall-clock time without changing the mathematics. Memory usage stays small because the solver keeps only a few counters and partial sums.
Gesucht sind Dreiecke mit ganzzahligen Eckpunkten \(A,B,C\in\mathbb{Z}^2\), deren drei Punkte auf einem Kreis um den Ursprung liegen und deren Schwerpunkt durch
$$A+B+C=(5,0)$$
festgelegt ist. Für jedes solche Dreieck mit Umfang höchstens der vorgegebenen Schranke wird der Umfang zum Endergebnis addiert. Das Programm gibt die Summe auf vier Dezimalstellen gerundet aus.
Aus dem Schwerpunkt \((5/3,0)\) folgt die Summenbedingung
$$H=(5,0).$$
Wählt man einen Eckpunkt \(C=(c_x,c_y)\), dann gilt
$$A+B=H-C=(5-c_x,-c_y).$$
Im Code heißt dieser Vektor \(S\). Damit reduziert sich die Aufgabe auf: Finde ganzzahlige Paare \(A,B\) mit Summe \(S\), gleichem Abstand vom Ursprung und passendem Umfang.
Setze
$$A=\frac{S+U}{2},\qquad B=\frac{S-U}{2},\qquad U:=A-B.$$
Dann sind \(A\) und \(B\) genau dann gleich weit vom Ursprung entfernt, wenn
$$U\perp S.$$
Für den gemeinsamen Radius \(R\) folgt außerdem
$$|U|^2=4R^2-|S|^2.$$
Diese Identität ist der zentrale Test im Solver.
Da \(S=(s_x,s_y)\) ganzzahlig ist, bilden alle ganzzahligen Orthogonalvektoren eine Rang-1-Gitterfamilie. Mit
$$g=\gcd(|s_x|,|s_y|),\qquad P=\left(-\frac{s_y}{g},\frac{s_x}{g}\right)$$
ist \(P\) der primitive ganzzahlige Normalvektor zu \(S\). Jeder ganzzahlige Orthogonalvektor ist daher
$$U=tP,\qquad t\in\mathbb{Z}.$$
Eingesetzt ergibt sich
$$t^2=\frac{(4R^2-|S|^2)g^2}{|S|^2}.$$
Der Code prüft genau diese Größe; sie muss ein vollständiges Quadrat sein, bevor \(A\) und \(B\) überhaupt rekonstruiert werden.
Aus \(A=(S+U)/2\) und \(B=(S-U)/2\) folgt sofort eine Paritätsbedingung: jede Koordinate von \(S\pm U\) muss gerade sein. Andernfalls wird der Kandidat verworfen.
Danach prüft das Programm, ob das Dreieck entartet ist. Dafür wird die doppelte Fläche per Kreuzprodukt bestimmt; ist sie null, liegen die Punkte auf einer Geraden und werden verworfen.
Damit jedes unlabeled triangle nur einmal gezählt wird, wird zusätzlich eine kanonische Vertauschungsregel benutzt: Der gewählte Punkt \(C\) muss lexikographisch nicht größer als \(A\) und \(B\) sein. Die feste Vorzeichenwahl des primitiven Normalvektors verhindert außerdem die doppelte Zählung durch Vertauschen von \(A\) und \(B\).
Die Suche läuft nicht blind über alle Radien. Zuerst bestimmt der Code eine obere Schranke für den Umkreisradius aus der Perimeterschranke.
Aus
$$AB^2=4R^2-|A+B|^2=4R^2-|H-C|^2$$
und der Dreiecksungleichung \(|H-C|\le |H|+|C|=5+R\) folgt
$$AB^2\ge 4R^2-(R+5)^2=3R^2-10R-25.$$
Dies gilt symmetrisch auch für die anderen Seiten, also
$$P\ge 3\sqrt{3R^2-10R-25}.$$
Die positive Lösung dieser Ungleichung liefert die im Programm verwendete Radiusgrenze. Danach werden nur noch Punkte \(C=(c_x,c_y)\) mit \(|C|\le R_{\max}\) untersucht. Weil \(C\) lexikographisch der kleinste Eckpunkt sein muss, reicht sogar \(c_x\le 1\); deshalb endet die äußere Schleife bei \(x=1\).
Das Programm teilt den \(c_x\)-Bereich in Blöcke auf und verteilt sie auf mehrere Threads. Jeder Thread führt eine lokale Summenbildung und Zählung durch; am Ende werden die Teilresultate zusammengeführt.
Exakte Tests verwenden ganzzahlige Arithmetik und eine Integer-Square-Root-Hilfsfunktion. Der endgültige Umfang wird mit long double berechnet und anschließend auf vier Dezimalstellen gerundet. Die Checkpoints im Code prüfen sowohl einen Beispielwert bei Umfangsgrenze 50 als auch die Übereinstimmung von Einzel- und Mehrthreadlauf.
Die Checkpoints sind konkret: Der Code verlangt round4(solve(50, 1)) = 291.0089 und prüft zusätzlich, dass solve(300, 1) mit einem Mehrthreadlauf übereinstimmt. Der erste Checkpoint validiert die Geometrie numerisch, der zweite die Parallelzerlegung.
Nehmen wir das gültige Dreieck
$$C=(-4,-3),\qquad A=(4,3),\qquad B=(5,0).$$
Alle drei Punkte erfüllen
$$|A|^2=|B|^2=|C|^2=25,$$
und außerdem
$$A+B+C=(4+5-4,\ 3+0-3)=(5,0).$$
Für dieses \(C\) erhält man
$$S=H-C=(9,3),\qquad g=\gcd(9,3)=3,\qquad P=(-1,3).$$
Die Radiusidentität liefert
$$t^2=\frac{(4\cdot 25-90)\cdot 3^2}{90}=1,$$
also \(t=1\) und damit
$$U=tP=(-1,3).$$
Die Rückrechnung ergibt
$$A=\frac{S+U}{2}=(4,3),\qquad B=\frac{S-U}{2}=(5,0).$$
Genau so arbeitet der Code für jedes zulässige \(C\): erst \(S\) bilden, dann prüfen, ob das induzierte \(t^2\) ein Quadrat ist, und schließlich \(A\) und \(B\) algebraisch rekonstruieren statt alle Dreiecks-Tupel zu enumerieren.
Das Programm akzeptiert --perimeter, --threads und --skip-checkpoints. Die Funktion solve wandelt die Umfangsschranke zuerst in eine Radiusgrenze \(R_{\max}\) um. Anschließend scannt sie ganzzahlige Punkte \(C=(c_x,c_y)\) im Kreis. Für jeden Kandidaten werden
$$S=(5-c_x,-c_y),\qquad r^2=|C|^2$$
gebildet. Danach folgen der primitive Orthogonalvektor, der Quadratscheck für \(t^2\), die Paritätsprüfung, die Rekonstruktion von \(A\) und \(B\), der Test auf Nicht-Entartung und die kanonische Prüfung sowie schließlich die genaue Umfangsgrenze.
Die Hilfsfunktionen isqrt_i64 und lex_leq kümmern sich um exakte Wurzel- bzw. Ordnungsprüfungen. Die Checkpoints vergleichen Einzel- und Mehrthreadausführung und prüfen zusätzlich die gespeicherte Beispielsumme für die Schranke 50.
Die Hauptarbeit besteht im Scan der zulässigen Gitterpunkte \(C\) innerhalb der Radiusgrenze. Für jeden Kandidaten fallen nur konstante viele arithmetische, gcd- und Wurzeltests an. Da zusätzlich \(c_x\le 1\) gilt, ist der Suchraum deutlich kleiner als die Menge aller Dreieckspermutationen.
Die Laufzeit wächst näherungsweise quadratisch mit der Radiusgrenze. Der Speicherbedarf bleibt klein, weil nur wenige Zähler und Teilsummen gehalten werden.
Orijine merkezli aynı çember üzerinde bulunan ve tam sayı koordinatlı \(A,B,C\in\mathbb{Z}^2\) üçgenleri aranır. Ağırlık merkezi
$$A+B+C=(5,0)$$
olmalıdır. Çevresi verilen üst sınırı aşmayan tüm farklı üçgenlerin çevreleri toplanır; program sonucu dört ondalık basamağa yuvarlayarak yazdırır.
Ağırlık merkezi \((5/3,0)\) olduğundan köşe toplamı
$$H=(5,0)$$
olur. Bir köşe \(C=(c_x,c_y)\) seçildiğinde
$$A+B=H-C=(5-c_x,-c_y)$$
elde edilir. Kod bu vektöre \(S\) der. Böylece problem, \(S\) toplamına sahip, orijine eşit uzaklıkta iki tam sayı nokta bulma problemine dönüşür.
Şu yazımı kullanırız:
$$A=\frac{S+U}{2},\qquad B=\frac{S-U}{2},\qquad U:=A-B.$$
Buradan \(A\) ile \(B\) aynı yarıçapta ise ve ancak ise
$$U\perp S$$
olur. Ortak yarıçap \(R\) için ayrıca
$$|U|^2=4R^2-|S|^2$$
bağıntısı gelir. Bu, kodun ana cebirsel testi olarak kullanılır.
\(S=(s_x,s_y)\) tam sayılı olduğundan, ona dik tam sayı vektörler tek boyutlu bir kafes oluşturur. Şu tanım yapılır:
$$g=\gcd(|s_x|,|s_y|),\qquad P=\left(-\frac{s_y}{g},\frac{s_x}{g}\right).$$
Bu \(P\), \(S\)'nin asal tam sayı normal vektörüdür. O halde her tam sayı dik vektör
$$U=tP,\qquad t\in\mathbb{Z}$$
şeklindedir. Yerine koyunca
$$t^2=\frac{(4R^2-|S|^2)g^2}{|S|^2}$$
olur. Kod tam olarak bu değerin tam kare olup olmadığını kontrol eder.
\(A\) ve \(B\) koordinatları \((S\pm U)/2\) ile geldiği için her bileşenin çift olması gerekir; aksi halde aday doğrudan elenir.
Daha sonra üçgenin dejenere olup olmadığı kontrol edilir. Bunun için çapraz çarpımdan çift alan hesaplanır; sıfır çıkarsa noktalar doğrusaldır ve üçgen atılır.
Yinelemeleri önlemek için kanonik bir seçim yapılır: seçilen \(C\) noktası, \(A\) ve \(B\)'den sözlük sıralamasında büyük olamaz. Asal normal vektör için sabit işaret seçimi de \(A\leftrightarrow B\) değişimini tekilleştirir.
Önce yarıçap için bir üst sınır çıkarılır. Şu eşitlikten başlayalım:
$$AB^2=4R^2-|A+B|^2=4R^2-|H-C|^2.$$
\(|H-C|\le |H|+|C|=5+R\) olduğundan
$$AB^2\ge 4R^2-(R+5)^2=3R^2-10R-25$$
elde edilir. Aynı alt sınır diğer kenarlar için de geçerlidir; dolayısıyla
$$P\ge 3\sqrt{3R^2-10R-25}.$$
Bu eşitsizliği \(R\) için çözdüğümüzde programın kullandığı \(R_{\max}\) sınırı çıkar. Bundan sonra yalnızca \(|C|\le R_{\max}\) olan tam sayı noktalar taranır. Ayrıca \(C\) sözlük sıralamasında en küçük köşe olmalıdır; bu yüzden dış döngüde \(c_x\le 1\) yeterlidir ve tarama \(x=1\)'de durur.
Program \(c_x\) aralığını bloklara ayırıp iş parçacıklarına dağıtır. Her iş parçacığı kendi yerel toplamını ve sayaçlarını tutar; sonunda parçalar birleştirilir.
Tamlık isteyen kontrollerde tam sayı aritmetiği ve integer square root yardımcıları kullanılır. Nihai çevre toplamı long double ile hesaplanır ve dört basamağa yuvarlanır. Kod içindeki checkpoint'ler hem örnek sonucu hem de tek iş parçacıklı ve çok iş parçacıklı çalışmanın aynı çıktıyı verdiğini denetler.
Checkpoint'ler somuttur: kod round4(solve(50, 1)) = 291.0089 eşitliğini zorunlu tutar ve ayrıca solve(300, 1) sonucunun çok iş parçacıklı koşuyla aynı olduğunu kontrol eder. İlk checkpoint geometrik hattı sayısal olarak, ikincisi ise paralel bölmeyi doğrular.
Somut bir geçerli örnek olarak
$$C=(-4,-3),\qquad A=(4,3),\qquad B=(5,0)$$
üçgenini alalım. Bu üç köşe için
$$|A|^2=|B|^2=|C|^2=25$$
ve ayrıca
$$A+B+C=(4+5-4,\ 3+0-3)=(5,0)$$
sağlanır. Bu \(C\) seçimi için
$$S=H-C=(9,3),\qquad g=\gcd(9,3)=3,\qquad P=(-1,3)$$
olur. Yarıçap bağıntısı
$$t^2=\frac{(4\cdot 25-90)\cdot 3^2}{90}=1$$
verir; dolayısıyla \(t=1\) ve
$$U=tP=(-1,3)$$
elde edilir. Geri kurunca
$$A=\frac{S+U}{2}=(4,3),\qquad B=\frac{S-U}{2}=(5,0)$$
çıkar. Kod her uygun \(C\) için tam olarak bunu yapar: önce \(S\)'yi kurar, sonra oluşan \(t^2\)'nin kare olup olmadığını sınar ve son olarak tüm köşe üçlülerini denemek yerine \(A\) ile \(B\)'yi cebirsel olarak geri kurar.
Program --perimeter, --threads ve --skip-checkpoints seçeneklerini destekler. solve fonksiyonu önce çevre sınırından \(R_{\max}\) yarıçap sınırını çıkarır. Sonra dairesel bölgede \(C=(c_x,c_y)\) tam sayı noktalarını tarar. Her aday için
$$S=(5-c_x,-c_y),\qquad r^2=|C|^2$$
kurulur. Ardından asal dik vektör, \(t^2\) kare testi, parite denetimi, \(A\) ve \(B\) rekonstrüksiyonu, dejenere olmama, kanonik düzen ve son olarak tam çevre filtresi uygulanır.
isqrt_i64 ve lex_leq yardımcıları sırasıyla tam kare testi ve sözlük sıralaması için kullanılır. Checkpoint kısmı tek iş parçacıklı ve çok iş parçacıklı sonuçları karşılaştırır ve çevre 50 için saklanan örnek toplamı doğrular.
Ana maliyet, yarıçap sınırı içindeki uygun \(C\) kafes noktalarını taramaktır. Her aday için yalnızca sabit sayıda aritmetik, gcd ve karekök testi yapılır. Ayrıca \(c_x\le 1\) kısıtı olduğundan arama alanı tüm üçgen permütasyonlarından çok daha küçüktür.
Zaman karmaşıklığı yaklaşık olarak yarıçap sınırıyla karesel büyür. Bellek kullanımı ise sadece birkaç sayaç ve yerel toplam tutulduğu için küçüktür.
Se buscan triángulos con vértices enteros \(A,B,C\in\mathbb{Z}^2\) que están sobre una misma circunferencia centrada en el origen y cuyo centroide satisface
$$A+B+C=(5,0).$$
Para cada triángulo con perímetro no mayor que el límite dado, se suma su perímetro. El programa imprime la suma final redondeada a cuatro decimales.
Como el centroide es \((5/3,0)\), la suma de vértices es
$$H=(5,0).$$
Si fijamos un vértice \(C=(c_x,c_y)\), entonces los otros dos satisfacen
$$A+B=H-C=(5-c_x,-c_y).$$
El código llama a este vector \(S\). Así, el problema se reduce a encontrar pares enteros \(A,B\) con suma \(S\), misma distancia al origen y perímetro correcto.
Escribimos
$$A=\frac{S+U}{2},\qquad B=\frac{S-U}{2},\qquad U:=A-B.$$
Entonces \(A\) y \(B\) tienen el mismo radio si y solo si
$$U\perp S.$$
Además, para el radio común \(R\) se cumple
$$|U|^2=4R^2-|S|^2.$$
Esta identidad es el filtro algebraico principal del algoritmo.
Como \(S=(s_x,s_y)\) es entero, los vectores enteros ortogonales forman una familia de rango 1. Definimos
$$g=\gcd(|s_x|,|s_y|),\qquad P=\left(-\frac{s_y}{g},\frac{s_x}{g}\right).$$
Ese \(P\) es el vector normal entero primitivo. Por tanto, todo vector ortogonal entero es
$$U=tP,\qquad t\in\mathbb{Z}.$$
Al sustituirlo obtenemos
$$t^2=\frac{(4R^2-|S|^2)g^2}{|S|^2}.$$
El programa comprueba exactamente que esta cantidad sea un cuadrado perfecto antes de reconstruir \(A\) y \(B\).
Como \(A=(S+U)/2\) y \(B=(S-U)/2\), cada coordenada de \(S\pm U\) debe ser par; si no, el candidato se descarta.
Después se rechazan los triángulos degenerados comprobando que el área doble, calculada con un producto cruzado, sea distinta de cero.
Para no contar varias veces el mismo triángulo no etiquetado, se exige una forma canónica: el vértice elegido \(C\) debe ser lexicográficamente no mayor que \(A\) ni que \(B\). La elección fija del signo del vector normal primitivo elimina además la simetría \(A\leftrightarrow B\).
El programa no prueba radios sin límite. Primero deduce una cota superior para el circunradio a partir de la cota del perímetro.
Usando
$$AB^2=4R^2-|A+B|^2=4R^2-|H-C|^2$$
y la desigualdad triangular \(|H-C|\le |H|+|C|=5+R\), obtenemos
$$AB^2\ge 4R^2-(R+5)^2=3R^2-10R-25.$$
La misma cota inferior vale simétricamente para los otros lados, así que
$$P\ge 3\sqrt{3R^2-10R-25}.$$
Resolver esta desigualdad da la cota \(R_{\max}\) usada por el programa. Después solo se recorren puntos enteros \(C\) con \(|C|\le R_{\max}\). Como \(C\) debe ser el vértice lexicográficamente más pequeño, basta con \(c_x\le 1\); por eso el barrido exterior termina en \(x=1\).
La implementación divide el rango de \(c_x\) en bloques y los reparte entre hilos. Cada hilo acumula su suma y su conteo local, y al final se combinan los resultados parciales.
Las pruebas que requieren exactitud usan aritmética entera y una rutina de raíz entera. El perímetro final se calcula con long double y luego se redondea a cuatro decimales. Los checkpoints verifican tanto un valor de ejemplo para límite 50 como la coincidencia entre una ejecución de un hilo y una multihilo.
Los checkpoints son concretos: el código exige round4(solve(50, 1)) = 291.0089 y además comprueba que solve(300, 1) coincida con una ejecución multihilo. El primero valida numéricamente la tubería geométrica y el segundo valida que la partición paralela no cambie el resultado.
Tomemos el triángulo válido
$$C=(-4,-3),\qquad A=(4,3),\qquad B=(5,0).$$
Los tres vértices cumplen
$$|A|^2=|B|^2=|C|^2=25,$$
y además
$$A+B+C=(4+5-4,\ 3+0-3)=(5,0).$$
Para esta elección de \(C\) obtenemos
$$S=H-C=(9,3),\qquad g=\gcd(9,3)=3,\qquad P=(-1,3).$$
La identidad del radio da
$$t^2=\frac{(4\cdot 25-90)\cdot 3^2}{90}=1,$$
así que \(t=1\) y por tanto
$$U=tP=(-1,3).$$
Al reconstruir obtenemos
$$A=\frac{S+U}{2}=(4,3),\qquad B=\frac{S-U}{2}=(5,0).$$
Eso es exactamente lo que hace el código para cada \(C\) admisible: formar \(S\), comprobar si el \(t^2\) inducido es un cuadrado perfecto y luego reconstruir \(A\) y \(B\) algebraicamente en vez de enumerar todos los triples de vértices.
El programa acepta --perimeter, --threads y --skip-checkpoints. La función solve convierte primero la cota de perímetro en una cota de radio \(R_{\max}\). Luego recorre puntos enteros \(C=(c_x,c_y)\) en el disco. Para cada candidato forma
$$S=(5-c_x,-c_y),\qquad r^2=|C|^2.$$
Después calcula el vector ortogonal primitivo, comprueba que \(t^2\) sea un cuadrado perfecto, verifica la paridad, reconstruye \(A\) y \(B\), rechaza triángulos degenerados o no canónicos y, por último, aplica la cota exacta del perímetro.
Los ayudantes isqrt_i64 y lex_leq se encargan de la raíz exacta y del orden canónico. Los checkpoints comparan la ejecución de un hilo con la multihilo y también validan la suma de ejemplo para perímetro 50.
El coste principal es el barrido de los puntos de red \(C\) dentro de la cota de radio. Para cada candidato solo hay un número constante de pruebas aritméticas, de gcd y de raíz. Además, como \(c_x\le 1\), el espacio de búsqueda es mucho menor que el conjunto de todas las permutaciones de triángulos.
El tiempo crece aproximadamente de forma cuadrática con la cota de radio. La memoria permanece pequeña porque solo se guardan unos pocos contadores y sumas parciales.
我们寻找整数顶点三角形 \(A,B,C\in\mathbb{Z}^2\)，要求三点都位于以原点为圆心的同一圆上，并满足
$$A+B+C=(5,0).$$
对于周长不超过给定上限的所有这样的三角形，把周长累加起来。程序最终输出保留四位小数的总和。
因为重心是 \((5/3,0)\)，所以顶点和为
$$H=(5,0).$$
若固定一个顶点 \(C=(c_x,c_y)\)，则另外两个顶点满足
$$A+B=H-C=(5-c_x,-c_y).$$
代码把这个向量记为 \(S\)。于是问题变成：寻找满足和为 \(S\)、到原点距离相同、且周长合格的整数点对 \(A,B\)。
写成
$$A=\frac{S+U}{2},\qquad B=\frac{S-U}{2},\qquad U:=A-B.$$
那么 \(A\) 和 \(B\) 到原点距离相等当且仅当
$$U\perp S.$$
若公共半径为 \(R\)，则还必须有
$$|U|^2=4R^2-|S|^2.$$
这就是程序中的核心代数测试。
由于 \(S=(s_x,s_y)\) 是整数向量，所有与它垂直的整数向量构成一条一维格点族。设
$$g=\gcd(|s_x|,|s_y|),\qquad P=\left(-\frac{s_y}{g},\frac{s_x}{g}\right).$$
那么 \(P\) 是 \(S\) 的原始整数法向量。所有整数垂直向量都可写成
$$U=tP,\qquad t\in\mathbb{Z}.$$
代回后得到
$$t^2=\frac{(4R^2-|S|^2)g^2}{|S|^2}.$$
程序在真正构造 \(A,B\) 之前，就会检查这个量是否是完全平方数。
因为 \(A=(S+U)/2\) 和 \(B=(S-U)/2\)，所以 \(S\pm U\) 的每个坐标都必须是偶数，否则候选直接丢弃。
随后用叉积检查三角形是否退化；若双倍面积为 0，则三点共线。
为了避免同一个无标签三角形被重复计数，代码只保留一种规范表示：所选的 \(C\) 必须在字典序上不大于 \(A\) 和 \(B\)。而原始法向量固定符号，则消除了 \(A\leftrightarrow B\) 的交换重复。
程序不会盲目枚举所有半径。它先从周长上界推导出外接圆半径的上界。
从
$$AB^2=4R^2-|A+B|^2=4R^2-|H-C|^2$$
和三角不等式 \(|H-C|\le |H|+|C|=5+R\) 得到
$$AB^2\ge 4R^2-(R+5)^2=3R^2-10R-25.$$
同样的下界对另外两条边也成立，因此
$$P\ge 3\sqrt{3R^2-10R-25}.$$
解这个不等式就得到程序中的半径上界 \(R_{\max}\)。之后只需扫描满足 \(|C|\le R_{\max}\) 的整数点。又因为 \(C\) 必须是字典序最小的顶点，所以只需扫描到 \(c_x\le 1\)，这就是外层循环在 \(x=1\) 结束的原因。
实现把 \(c_x\) 范围切成若干块分给多个线程。每个线程维护自己的局部和局部计数，最后再合并。
需要精确性的地方使用整数运算和整数平方根辅助函数。最终周长用 long double 计算，再四舍五入到四位小数。代码里的检查项同时验证了单线程和多线程结果一致，并检查了周长 50 的样例和。
这些 checkpoint 是具体的：代码要求 round4(solve(50, 1)) = 291.0089，还要求 solve(300, 1) 与多线程运行一致。前者从数值上验证几何管线，后者验证并行拆分没有改变结果。
看一个实际成立的三角形
$$C=(-4,-3),\qquad A=(4,3),\qquad B=(5,0).$$
三个顶点都满足
$$|A|^2=|B|^2=|C|^2=25,$$
并且
$$A+B+C=(4+5-4,\ 3+0-3)=(5,0).$$
对这个 \(C\)，有
$$S=H-C=(9,3),\qquad g=\gcd(9,3)=3,\qquad P=(-1,3).$$
半径恒等式给出
$$t^2=\frac{(4\cdot 25-90)\cdot 3^2}{90}=1,$$
所以 \(t=1\)，从而
$$U=tP=(-1,3).$$
回代即可得到
$$A=\frac{S+U}{2}=(4,3),\qquad B=\frac{S-U}{2}=(5,0).$$
代码对每个可行的 \(C\) 做的正是这件事：先构造 \(S\)，判断诱导出的 \(t^2\) 是否为完全平方数，再代数式重建 \(A\) 和 \(B\)，而不是暴力枚举所有顶点三元组。
程序支持 --perimeter、--threads 和 --skip-checkpoints。solve 先把周长上界换成半径上界 \(R_{\max}\)，再在圆盘内扫描整数点 \(C=(c_x,c_y)\)。对每个候选点，构造
$$S=(5-c_x,-c_y),\qquad r^2=|C|^2.$$
接着计算原始垂直向量，检查 \(t^2\) 是否为完全平方数，验证奇偶性，重建 \(A\) 和 \(B\)，排除退化与非规范情况，最后再用精确周长条件筛选一次。
isqrt_i64 和 lex_leq 分别负责整数平方根和字典序判断。检查器会比较单线程与多线程版本，并验证周长 50 的存储样例。
主要开销是扫描半径上界内的整数点 \(C\)。每个候选只做常数次代数、gcd 和平方检查。再加上 \(c_x\le 1\) 的限制，搜索空间比所有三角形排列小得多。
时间大致随半径上界呈二次增长。空间开销很小，因为只保存少量计数器和局部和。
Перебираются треугольники с целыми вершинами \(A,B,C\in\mathbb{Z}^2\), у которых все три точки лежат на одной окружности с центром в начале координат и удовлетворяют условию
$$A+B+C=(5,0).$$
Для всех таких треугольников с периметром не выше заданного предела суммируется периметр. Программа выводит итог, округлённый до четырёх знаков после запятой.
Так как центр масс равен \((5/3,0)\), сумма вершин равна
$$H=(5,0).$$
Если зафиксировать вершину \(C=(c_x,c_y)\), то для остальных двух вершин получаем
$$A+B=H-C=(5-c_x,-c_y).$$
В коде этот вектор называется \(S\). Теперь задача сводится к поиску целочисленных пар \(A,B\) с суммой \(S\), одинаковым расстоянием до начала координат и подходящим периметром.
Запишем
$$A=\frac{S+U}{2},\qquad B=\frac{S-U}{2},\qquad U:=A-B.$$
Тогда \(A\) и \(B\) равноудалены от начала координат тогда и только тогда, когда
$$U\perp S.$$
Для общего радиуса \(R\) имеем также
$$|U|^2=4R^2-|S|^2.$$
Это центральная алгебраическая проверка алгоритма.
Поскольку \(S=(s_x,s_y)\) целочисленен, все целые векторы, ортогональные \(S\), образуют одномерное множество решётки. Пусть
$$g=\gcd(|s_x|,|s_y|),\qquad P=\left(-\frac{s_y}{g},\frac{s_x}{g}\right).$$
Тогда \(P\) — примитивный целый нормальный вектор к \(S\). Значит, любой целый ортогональный вектор имеет вид
$$U=tP,\qquad t\in\mathbb{Z}.$$
После подстановки получаем
$$t^2=\frac{(4R^2-|S|^2)g^2}{|S|^2}.$$
Именно эту величину программа проверяет на полно-квадратность до реконструкции \(A\) и \(B\).
Из формул \(A=(S+U)/2\) и \(B=(S-U)/2\) следует необходимость чётности: каждая координата \(S\pm U\) должна быть чётной, иначе кандидат отвергается.
Затем треугольник проверяется на вырождение: если удвоенная площадь, вычисленная через векторное произведение, равна нулю, точки лежат на одной прямой.
Чтобы не считать один и тот же неориентированный треугольник несколько раз, используется канонический выбор: выбранная вершина \(C\) должна быть лексикографически не больше, чем \(A\) и \(B\). Фиксированный знак примитивного нормального вектора убирает также симметрию \(A\leftrightarrow B\).
Сначала код выводит верхнюю границу для радиуса описанной окружности из ограничения на периметр.
Из
$$AB^2=4R^2-|A+B|^2=4R^2-|H-C|^2$$
и неравенства треугольника \(|H-C|\le |H|+|C|=5+R\) получаем
$$AB^2\ge 4R^2-(R+5)^2=3R^2-10R-25.$$
Такая же нижняя оценка верна для остальных сторон, поэтому
$$P\ge 3\sqrt{3R^2-10R-25}.$$
Решение этого неравенства даёт границу \(R_{\max}\), используемую в программе. После этого перебираются только точки \(C\) с \(|C|\le R_{\max}\). Поскольку \(C\) должен быть лексикографически минимальной вершиной, достаточно проверять \(c_x\le 1\); поэтому внешний цикл останавливается на \(x=1\).
Реализация делит диапазон \(c_x\) на блоки и распределяет их по потокам. Каждый поток ведёт свою локальную сумму и счётчик, после чего частичные результаты объединяются.
Точные проверки используют целочисленную арифметику и помощник для целочисленного квадратного корня. Итоговый периметр считается в long double и затем округляется до четырёх знаков. Контрольные проверки сравнивают однопоточную и многопоточную версии и отдельно проверяют сохранённую сумму для границы 50.
Эти checkpoint'ы вполне конкретны: код требует round4(solve(50, 1)) = 291.0089 и дополнительно проверяет, что solve(300, 1) совпадает с многопоточным запуском. Первый checkpoint численно валидирует геометрический конвейер, второй проверяет корректность распараллеливания.
Возьмём корректный треугольник
$$C=(-4,-3),\qquad A=(4,3),\qquad B=(5,0).$$
Все три вершины удовлетворяют
$$|A|^2=|B|^2=|C|^2=25,$$
и также
$$A+B+C=(4+5-4,\ 3+0-3)=(5,0).$$
Для этого выбора \(C\) получаем
$$S=H-C=(9,3),\qquad g=\gcd(9,3)=3,\qquad P=(-1,3).$$
Радиусное тождество даёт
$$t^2=\frac{(4\cdot 25-90)\cdot 3^2}{90}=1,$$
поэтому \(t=1\) и значит
$$U=tP=(-1,3).$$
Обратная реконструкция даёт
$$A=\frac{S+U}{2}=(4,3),\qquad B=\frac{S-U}{2}=(5,0).$$
Именно это код и делает для каждого допустимого \(C\): строит \(S\), проверяет, является ли индуцированное \(t^2\) полным квадратом, и затем алгебраически восстанавливает \(A\) и \(B\), а не перебирает все тройки вершин.
Программа поддерживает параметры --perimeter, --threads и --skip-checkpoints. Функция solve сначала превращает ограничение на периметр в границу радиуса \(R_{\max}\). Затем она перебирает целые точки \(C=(c_x,c_y)\) внутри круга. Для каждого кандидата строятся
$$S=(5-c_x,-c_y),\qquad r^2=|C|^2.$$
После этого вычисляется примитивный ортогональный вектор, проверяется, что \(t^2\) является полным квадратом, проверяется чётность, восстанавливаются \(A\) и \(B\), исключаются вырожденные и неканонические треугольники, и только затем применяется точная граница по периметру.
Вспомогательные функции isqrt_i64 и lex_leq отвечают за точный корень и лексикографический порядок. Контрольные проверки сравнивают одно- и многопоточный запуск и проверяют примерную сумму для периметра 50.
Основная стоимость — перебор точек решётки \(C\) внутри радиусной границы. Для каждого кандидата выполняется только константное число арифметических, gcd- и корневых проверок. Кроме того, ограничение \(c_x\le 1\) существенно уменьшает пространство поиска.
Время растёт примерно квадратично по радиусной границе. Память остаётся небольшой, так как хранятся только несколько счётчиков и частичных сумм.
نبحث عن مثلثات ذات رؤوس صحيحة \(A,B,C\in\mathbb{Z}^2\) بحيث تقع النقاط الثلاث على دائرة واحدة مركزها الأصل، ويكون
$$A+B+C=(5,0).$$
لكل مثلث لا يتجاوز محيطه الحد المعطى، نضيف المحيط إلى المجموع النهائي. يطبع البرنامج الناتج بعد تقريبه إلى أربع منازل عشرية.
بما أن مركز الكتلة هو \((5/3,0)\)، فإن مجموع الرؤوس يساوي
$$H=(5,0).$$
إذا ثبتنا الرأس \(C=(c_x,c_y)\)، فإن الرأسين الآخرين يحققان
$$A+B=H-C=(5-c_x,-c_y).$$
يسمي الكود هذا المتجه \(S\). وهكذا تصبح المسألة: إيجاد زوجين صحيحين \(A,B\) لهما المجموع \(S\)، ويقعان على نفس البعد من الأصل، ويعطيان محيطًا مقبولًا.
نكتب
$$A=\frac{S+U}{2},\qquad B=\frac{S-U}{2},\qquad U:=A-B.$$
عندئذٍ يكون \(A\) و\(B\) على نفس نصف القطر إذا وفقط إذا
$$U\perp S.$$
ولنصف القطر المشترك \(R\) نحصل أيضًا على
$$|U|^2=4R^2-|S|^2.$$
هذه هي الاختبار الجبري الأساسي في الحل.
بما أن \(S=(s_x,s_y)\) متجه صحيح، فإن كل المتجهات الصحيحة العمودية عليه تشكل عائلة شبكية من رتبة واحدة. نعرّف
$$g=\gcd(|s_x|,|s_y|),\qquad P=\left(-\frac{s_y}{g},\frac{s_x}{g}\right).$$
عندها يكون \(P\) هو متجه العمود الصحيح الأولي لـ\(S\). لذلك أي متجه عمودي صحيح يكتب
$$U=tP,\qquad t\in\mathbb{Z}.$$
وبالتعويض نحصل على
$$t^2=\frac{(4R^2-|S|^2)g^2}{|S|^2}.$$
يفحص البرنامج هذه الكمية مباشرة، ويجب أن تكون مربعًا كاملًا قبل إعادة بناء \(A\) و\(B\).
بما أن \(A=(S+U)/2\) و\(B=(S-U)/2\)، فكل مركبة في \(S\pm U\) يجب أن تكون زوجية؛ وإلا يُرفض المرشح فورًا.
بعد ذلك يفحص البرنامج ما إذا كان المثلث منعدم المساحة باستخدام الجداء الاتجاهي؛ فإذا كانت المساحة المضاعفة صفرًا فالنقاط على استقامة واحدة.
ولتجنب العد المكرر للمثلث نفسه دون تسمية، يُستخدم تمثيل معياري: يجب أن يكون الرأس المختار \(C\) أصغر أو مساوياً للرأسين \(A\) و\(B\) ترتيبًا معجميًا. كما أن اختيار إشارة المتجه العمودي الأولي يزيل التماثل بين \(A\) و\(B\).
لا يمسح البرنامج كل الأنصاف أقطار بلا قيد. أولًا يستخرج حدًا أعلى لنصف قطر الدائرة المحيطة من حد المحيط.
من العلاقة
$$AB^2=4R^2-|A+B|^2=4R^2-|H-C|^2$$
وباستعمال متباينة المثلث \(|H-C|\le |H|+|C|=5+R\) نحصل على
$$AB^2\ge 4R^2-(R+5)^2=3R^2-10R-25.$$
وينطبق الحد الأدنى نفسه على الأضلاع الأخرى، لذا
$$P\ge 3\sqrt{3R^2-10R-25}.$$
بحل هذه المتباينة نحصل على \(R_{\max}\) المستخدم في البرنامج. بعد ذلك لا يُفحص إلا كل نقطة صحيحة \(C\) تحقق \(|C|\le R_{\max}\). وبما أن \(C\) يجب أن يكون أصغر رأس ترتيبًا معجميًا، يكفي فحص \(c_x\le 1\)؛ ولهذا تتوقف الحلقة الخارجية عند \(x=1\).
يقسم التنفيذ مجال \(c_x\) إلى كتل ويوزعها على الخيوط. كل خيط يحتفظ بمجموعه وعدّاده المحلي، ثم تُجمع النتائج الجزئية في النهاية.
التفقدات التي تحتاج إلى دقة تستخدم الحساب الصحيح ودالة الجذر الصحيح. أما المحيط النهائي فيُحسب بـ long double ثم يُقرب إلى أربع منازل عشرية. نقاط التحقق داخل الكود تقارن بين النسخة أحادية الخيط ومتعددة الخيوط، وتفحص أيضًا قيمة العينة عند حد 50.
ونقاط التحقق هنا ملموسة: فالكود يفرض round4(solve(50, 1)) = 291.0089، ويتحقق أيضًا من أن solve(300, 1) يطابق تشغيلًا متعدد الخيوط. تتحقق النقطة الأولى من المسار الهندسي عدديًا، بينما تتحقق الثانية من أن التقسيم المتوازي لا يغيّر النتيجة.
لنأخذ مثلثًا صحيحًا هو
$$C=(-4,-3),\qquad A=(4,3),\qquad B=(5,0).$$
هذه الرؤوس الثلاثة تحقق
$$|A|^2=|B|^2=|C|^2=25,$$
وكذلك
$$A+B+C=(4+5-4,\ 3+0-3)=(5,0).$$
لهذا الاختيار من \(C\) نحصل على
$$S=H-C=(9,3),\qquad g=\gcd(9,3)=3,\qquad P=(-1,3).$$
وتعطي هوية نصف القطر
$$t^2=\frac{(4\cdot 25-90)\cdot 3^2}{90}=1,$$
ومن ثم \(t=1\) وبالتالي
$$U=tP=(-1,3).$$
وبإعادة البناء نحصل على
$$A=\frac{S+U}{2}=(4,3),\qquad B=\frac{S-U}{2}=(5,0).$$
وهذا بالضبط ما يفعله الكود لكل \(C\) مقبول: يبني \(S\)، ثم يفحص هل \(t^2\) الناتج مربع كامل، ثم يعيد بناء \(A\) و\(B\) جبريًا بدل تعداد جميع ثلاثيات الرؤوس.
يدعم البرنامج الخيارات --perimeter و--threads و--skip-checkpoints. تبدأ الدالة solve بتحويل حد المحيط إلى حد لنصف القطر \(R_{\max}\). ثم تمسح نقاط الشبكة الصحيحة \(C=(c_x,c_y)\) داخل القرص. لكل مرشح تُبنى
$$S=(5-c_x,-c_y),\qquad r^2=|C|^2.$$
بعد ذلك تُحسب المتجهات العمودية الأولية، ويُفحص ما إذا كانت \(t^2\) مربعًا كاملاً، ثم يُتحقق من الفردية، ثم يُعاد بناء \(A\) و\(B\)، وتُرفض المثلثات المنعدمة أو غير المعيارية، وأخيرًا يُطبق شرط المحيط الدقيق.
تتكفل الدالتان isqrt_i64 وlex_leq باختبار الجذر الصحيح والترتيب المعجمي. كما تقارن نقاط التحقق بين التنفيذ أحادي الخيط ومتعدد الخيوط، وتتحقق أيضًا من مجموع العينة للمحيط 50.
الكلفة الأساسية هي مسح نقاط الشبكة \(C\) داخل حد نصف القطر. لكل مرشح لا توجد إلا اختبارات ثابتة العدد من الحسابات الصحيحة و\(\gcd\) والجذر. ومع قيد \(c_x\le 1\)، تصبح مساحة البحث أصغر بكثير من جميع تبديلات المثلثات الممكنة.
الزمن ينمو تقريبًا تربيعيًا مع حد نصف القطر. أما الذاكرة فتبقى صغيرة لأن البرنامج لا يحتفظ إلا بعدة عدادات ومجاميع جزئية.