We study integer-coordinate triangles \(A,B,C\) whose vertices lie in the closed disk
$$x^2+y^2\le r^2.$$
Among all such triangles with area
$$\Delta=\frac12,$$
the task is to maximize the perimeter. If several triangles reach the same perimeter, the one with larger circumradius \(R\) is preferred, and the reported quantity is
$$T(r)=\frac{R}{r}.$$
The brute-force search space is enormous, so the solution rewrites the geometry in terms of a primitive base edge and a one-dimensional lattice family for the third vertex.
Fix one candidate triangle and choose the side \(AB\) as the base. Write
$$u=B-A=(a,b),\qquad w=C-A,\qquad L=|u|=\sqrt{a^2+b^2}.$$
The implementations only keep configurations where the chosen base is the longest side, so
$$|w|\le L,\qquad |u-w|\le L.$$
For lattice points, the doubled area is the absolute determinant:
$$2\Delta=|\det(u,w)|.$$
Because \(\Delta=\frac12\), every admissible triangle satisfies
$$|\det(u,w)|=1.$$
If \(A=(x_A,y_A)\) and \(C=(x,y)\), then \(w=C-A\), so the same condition becomes
$$a y-b x=a y_A-b x_A\pm1.$$
This immediately forces \(\gcd(a,b)=1\); if \(a\) and \(b\) had a common factor \(g>1\), then the left-hand side would always be divisible by \(g\), so it could never equal \(\pm1\).
Since \(\gcd(a,b)=1\), the linear Diophantine equation
$$-b x+a y=1$$
has an integer solution. If the required right-hand side is some integer \(k\), one particular point on the line is obtained by scaling that solution by \(k\). Every other integer point on the same line differs by a multiple of the base vector \(u\), so the full family is
$$C(t)=C_0+t(a,b),\qquad t\in\mathbb{Z}.$$
Thus, once \(A\), \(B\), and the sign choice \(\pm1\) are fixed, the third vertex can only move along one lattice line parallel to the base.
Substituting \(C(t)=C_0+t u\) into the disk constraint gives
$$|C_0+t u|^2\le r^2,$$
which expands to the quadratic inequality
$$L^2 t^2+2(C_0\cdot u)t+\bigl(|C_0|^2-r^2\bigr)\le0.$$
The discriminant tells us whether that line meets the disk at all. When it does, the admissible integers form one contiguous interval
$$t_{\min}\le t\le t_{\max}.$$
The implementations compute those endpoints with exact integer floor and ceiling arithmetic, so the feasibility test does not depend on floating-point rounding.
Let
$$q=u\cdot w.$$
This is an integer because both vectors have integer coordinates. Lagrange's identity gives
$$|u|^2|w|^2=(u\cdot w)^2+\det(u,w)^2=q^2+1,$$
hence
$$|w|=\frac{\sqrt{q^2+1}}{L}.$$
For the third side, use \(u-w=B-C\). Then
$$u\cdot(u-w)=L^2-q,\qquad \det(u,u-w)=\det(u,w),$$
so
$$|u-w|=\frac{\sqrt{(L^2-q)^2+1}}{L}.$$
The perimeter therefore becomes
$$P=L+\frac{\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1}}{L}.$$
Because the chosen base must be the longest side, both \(q\) and \(L^2-q\) are positive integers. For every integer \(n\ge1\),
$$\sqrt{n^2+1}\le n+\frac{1}{2n}.$$
Apply this inequality once to \(q\) and once to \(L^2-q\):
$$\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1} \le q+\frac{1}{2q}+(L^2-q)+\frac{1}{2(L^2-q)} \le L^2+1.$$
After dividing by \(L\), we obtain
$$|w|+|u-w|\le L+\frac1L,$$
and therefore
$$\boxed{P\le2L+\frac1L.}$$
This is the key pruning inequality used by the search. Once even this optimistic upper bound drops below the best perimeter already found, no shorter base can improve the answer.
Any edge inside the disk has length at most \(2r\). For that reason, promising base edges are those with \(L\) very close to \(2r\). The implementations measure this gap by the deficiency
$$d=4r^2-L^2.$$
Small \(d\) means an almost diametral base, so candidate primitive edges are generated in increasing deficiency, or equivalently decreasing \(L\).
If the current best perimeter is \(P^*\), then a future edge can only win if
$$2L+\frac1L>P^*.$$
Solving the equality gives the larger root
$$L_{\min}=\frac{P^*+\sqrt{(P^*)^2-8}}{4}.$$
Hence no edge with \(L<L_{\min}\) can matter, and the search only needs to cover deficiencies up to
$$d_{\max}=4r^2-L_{\min}^2.$$
Take
$$A=(0,0),\qquad B=(2,1).$$
Then \(u=(2,1)\) and \(L^2=5\). The area condition becomes
$$|\det(u,C-A)|=|2y-x|=1.$$
Choose the \(+1\) branch. One integer point on the line \(2y-x=1\) is \((-1,0)\), so every solution has the form
$$C(t)=(-1,0)+t(2,1).$$
Inside the disk of radius \(3\), we need
$$(-1+2t)^2+t^2\le9,$$
which leaves \(t=0\) and \(t=1\). The choice \(t=1\) gives \(C=(1,1)\), and then
$$|C-A|^2=2,\qquad |C-B|^2=1,\qquad P=\sqrt5+\sqrt2+1.$$
Since \(\Delta=\frac12\), the circumradius is
$$R=\frac{|AB|\cdot|AC|\cdot|BC|}{4\Delta} =\frac{\sqrt5\cdot\sqrt2\cdot1}{2} =\frac{\sqrt{10}}{2}.$$
The implementation first precomputes, for each integer \(x\in[-r,r]\), the largest \(|y|\) still inside the disk. That allows fast testing of whether both endpoints of a translated base edge stay inside the circle.
Next it builds primitive edge vectors \((a,b)\) with \(1\le b\le a\), so rotational and reflection symmetries are not revisited. Only vectors whose squared length lies in the current deficiency window are kept, and they are processed from longer to shorter edges.
For each admissible translation of the base, the C++, Python, and Java implementations examine the two determinant lines corresponding to area \(+\frac12\) and \(-\frac12\). An integer point on the chosen line is produced with the extended Euclidean algorithm, then shifted along the base direction so the quadratic disk test stays numerically small and exact.
Every integer point in the resulting \(t\)-interval is checked. The implementation discards cases where the third point coincides with an endpoint or where one of the other two sides exceeds the base length. Surviving candidates are compared first by perimeter and then, on ties, by circumradius.
The C++ version evaluates edge batches in parallel, the Java version mirrors the same exact search with arbitrary-precision arithmetic where needed, and the Python version acts as a thin bridge that launches the native computation and extracts the final numeric answer.
Let \(E(D)\) be the number of primitive edge vectors whose deficiency is at most \(D\). Precomputing the disk boundary table costs \(O(r)\) time and \(O(r)\) memory. Generating and sorting the current candidate edges costs \(O(E(D)\log E(D))\).
For a single edge, the solver scans all translations that keep both endpoints in the disk; in the worst case this can be as large as \(O(r^2)\). Each valid translation yields at most two determinant lines, and each line contributes one contiguous interval of integer parameters for the third vertex. A deliberately loose bound for one search round is therefore \(O(r^2E(D))\), but in practice the deficiency window stays small, the perimeter bound removes many edges early, and the integer \(t\)-interval is usually short.
Overall, the method is strongly data-dependent but memory usage remains modest: \(O(r+E(D))\), plus thread-local state in the parallel C++ version.
Untersucht werden Gitterdreiecke \(A,B,C\), deren Ecken in der abgeschlossenen Kreisscheibe
$$x^2+y^2\le r^2$$
liegen. Unter allen solchen Dreiecken mit Fläche
$$\Delta=\frac12$$
soll der Umfang maximal werden. Haben mehrere Dreiecke denselben Umfang, wird das mit größerem Umkreisradius \(R\) bevorzugt, und ausgegeben wird
$$T(r)=\frac{R}{r}.$$
Eine rohe Vollsuche ist viel zu groß, daher organisiert die Lösung die Geometrie über eine primitive Grundkante und eine eindimensionale Gitterfamilie für den dritten Punkt.
Fixiere ein Kandidatendreieck und wähle \(AB\) als Grundkante. Schreibe
$$u=B-A=(a,b),\qquad w=C-A,\qquad L=|u|=\sqrt{a^2+b^2}.$$
Die Implementierungen behalten nur Fälle, in denen die gewählte Grundkante die längste Seite ist. Also gilt
$$|w|\le L,\qquad |u-w|\le L.$$
Für Gitterpunkte ist die doppelte Fläche der Betrag der Determinante:
$$2\Delta=|\det(u,w)|.$$
Wegen \(\Delta=\frac12\) muss also gelten
$$|\det(u,w)|=1.$$
Mit \(A=(x_A,y_A)\) und \(C=(x,y)\) ist \(w=C-A\), also wird daraus
$$a y-b x=a y_A-b x_A\pm1.$$
Damit folgt sofort \(\gcd(a,b)=1\). Hätten \(a\) und \(b\) einen gemeinsamen Teiler \(g>1\), dann wäre die linke Seite immer durch \(g\) teilbar und könnte nie \(\pm1\) sein.
Weil \(\gcd(a,b)=1\) ist, besitzt die lineare diophantische Gleichung
$$-b x+a y=1$$
eine ganzzahlige Lösung. Ist die gewünschte rechte Seite ein Integer \(k\), dann erhält man einen speziellen Punkt durch Skalierung mit \(k\). Alle anderen ganzzahligen Punkte auf derselben Geraden unterscheiden sich um ein ganzzahliges Vielfaches des Vektors \(u\). Also lautet die vollständige Familie
$$C(t)=C_0+t(a,b),\qquad t\in\mathbb{Z}.$$
Sobald \(A\), \(B\) und das Vorzeichen \(\pm1\) feststehen, kann sich der dritte Punkt also nur auf einer Gittergeraden parallel zur Grundkante bewegen.
Setzt man \(C(t)=C_0+t u\) in die Kreisschranke ein, so erhält man
$$|C_0+t u|^2\le r^2,$$
also die quadratische Ungleichung
$$L^2 t^2+2(C_0\cdot u)t+\bigl(|C_0|^2-r^2\bigr)\le0.$$
Die Diskriminante entscheidet, ob die Gerade die Kreisscheibe überhaupt trifft. Falls ja, bilden die zulässigen ganzen \(t\) genau ein zusammenhängendes Intervall
$$t_{\min}\le t\le t_{\max}.$$
Die Implementierungen berechnen diese Grenzen mit exakter ganzzahliger Auf- und Abrundung, also ohne numerische Unsicherheit in diesem Schritt.
Setze
$$q=u\cdot w.$$
Da beide Vektoren ganzzahlige Koordinaten besitzen, ist \(q\) ein Integer. Aus der Identität von Lagrange folgt
$$|u|^2|w|^2=(u\cdot w)^2+\det(u,w)^2=q^2+1,$$
und daher
$$|w|=\frac{\sqrt{q^2+1}}{L}.$$
Für die dritte Seite verwendet man \(u-w=B-C\). Dann gilt
$$u\cdot(u-w)=L^2-q,\qquad \det(u,u-w)=\det(u,w),$$
also
$$|u-w|=\frac{\sqrt{(L^2-q)^2+1}}{L}.$$
Damit hat der Umfang die Form
$$P=L+\frac{\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1}}{L}.$$
Weil die Grundkante die längste Seite sein muss, sind sowohl \(q\) als auch \(L^2-q\) positive ganze Zahlen. Für jedes \(n\ge1\) gilt
$$\sqrt{n^2+1}\le n+\frac{1}{2n}.$$
Wendet man das einmal auf \(q\) und einmal auf \(L^2-q\) an, so ergibt sich
$$\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1} \le q+\frac{1}{2q}+(L^2-q)+\frac{1}{2(L^2-q)} \le L^2+1.$$
Nach Division durch \(L\) folgt
$$|w|+|u-w|\le L+\frac1L,$$
also insgesamt
$$\boxed{P\le2L+\frac1L.}$$
Genau diese Schranke wird zum Pruning benutzt. Sobald sogar dieser optimistische Oberwert unter dem aktuellen Bestwert liegt, kann keine kürzere Grundkante mehr gewinnen.
Jede Kante innerhalb der Kreisscheibe hat Länge höchstens \(2r\). Gute Grundkanten sollten also \(L\) möglichst nahe an \(2r\) haben. Die Implementierungen messen den Abstand dazu mit dem Defizit
$$d=4r^2-L^2.$$
Kleines \(d\) bedeutet fast-diametrische Grundkante. Deshalb werden primitive Kanten in wachsendem Defizit, also fallendem \(L\), erzeugt.
Ist der aktuell beste Umfang \(P^*\), dann kann eine spätere Kante nur noch gewinnen, wenn
$$2L+\frac1L>P^*.$$
Die Gleichung liefert als größere Wurzel
$$L_{\min}=\frac{P^*+\sqrt{(P^*)^2-8}}{4}.$$
Daher sind Kanten mit \(L<L_{\min}\) irrelevant, und die Suche muss nur Defizite bis
$$d_{\max}=4r^2-L_{\min}^2$$
abdecken.
Nimm
$$A=(0,0),\qquad B=(2,1).$$
Dann ist \(u=(2,1)\) und \(L^2=5\). Die Flächenbedingung lautet
$$|\det(u,C-A)|=|2y-x|=1.$$
Wählt man den \(+1\)-Zweig, so erhält man die Gerade \(2y-x=1\). Ein Gitterpunkt darauf ist \((-1,0)\), also gilt allgemein
$$C(t)=(-1,0)+t(2,1).$$
Innerhalb der Kreisscheibe mit Radius \(3\) muss
$$(-1+2t)^2+t^2\le9$$
gelten, woraus \(t=0\) und \(t=1\) folgen. Für \(t=1\) erhält man \(C=(1,1)\). Dann ist
$$|C-A|^2=2,\qquad |C-B|^2=1,\qquad P=\sqrt5+\sqrt2+1.$$
Weil \(\Delta=\frac12\), ist der Umkreisradius
$$R=\frac{|AB|\cdot|AC|\cdot|BC|}{4\Delta} =\frac{\sqrt5\cdot\sqrt2\cdot1}{2} =\frac{\sqrt{10}}{2}.$$
Die Implementierung berechnet zuerst für jedes ganzzahlige \(x\in[-r,r]\) die größte erlaubte Höhe \(|y|\) innerhalb der Kreisscheibe. Dadurch kann später schnell geprüft werden, ob beide Endpunkte einer verschobenen Grundkante im Kreis liegen.
Danach werden primitive Kantenvektoren \((a,b)\) mit \(1\le b\le a\) aufgebaut, sodass Rotations- und Spiegelungssymmetrien nicht mehrfach durchlaufen werden. Berücksichtigt werden nur Vektoren, deren Quadrat der Länge im aktuellen Defizitfenster liegt; verarbeitet werden sie von langen zu kürzeren Kanten.
Für jede zulässige Translation der Grundkante betrachten die C++, Python- und Java-Implementierungen die beiden Determinantengeraden für Fläche \(+\frac12\) und \(-\frac12\). Ein Gitterpunkt auf der gewählten Geraden wird mit dem erweiterten euklidischen Algorithmus konstruiert und dann längs der Grundkante so verschoben, dass die anschließende quadratische Kreisschranke klein und exakt bleibt.
Jeder ganzzahlige Punkt im daraus entstehenden \(t\)-Intervall wird geprüft. Verworfen werden Fälle, in denen der dritte Punkt mit einem Endpunkt zusammenfällt oder eine der beiden anderen Seiten länger als die Grundkante ist. Übrig gebliebene Kandidaten werden zuerst nach Umfang und bei Gleichstand nach Umkreisradius verglichen.
Die C++-Version bearbeitet Kantenblöcke parallel, die Java-Version spiegelt dieselbe exakte Suche mit beliebig präziser Ganzzahlarithmetik an den kritischen Stellen, und die Python-Version dient als schlanke Brücke, die die native Berechnung startet und die Endzahl extrahiert.
Sei \(E(D)\) die Anzahl primitiver Kantenvektoren mit Defizit höchstens \(D\). Die Vorberechnung der Kreisrandtabelle benötigt \(O(r)\) Zeit und \(O(r)\) Speicher. Das Erzeugen und Sortieren der aktuellen Kandidatenkanten kostet \(O(E(D)\log E(D))\).
Für eine einzelne Kante werden alle Translationen durchlaufen, bei denen beide Endpunkte in der Kreisscheibe bleiben; im schlimmsten Fall kann das \(O(r^2)\) groß sein. Jede gültige Translation erzeugt höchstens zwei Determinantengeraden, und jede Gerade liefert genau ein zusammenhängendes Intervall ganzer Parameter für den dritten Punkt. Eine bewusst grobe Schranke für eine Suchrunde ist daher \(O(r^2E(D))\), praktisch aber deutlich kleiner, weil das Defizitfenster klein bleibt, die Umfangsschranke viele Kanten früh aussortiert und die \(t\)-Intervalle meist kurz sind.
Insgesamt ist die Laufzeit stark datenabhängig, während der Speicherverbrauch moderat bleibt: \(O(r+E(D))\), zuzüglich thread-lokaler Zustände in der parallelen C++-Version.
Köşeleri
$$x^2+y^2\le r^2$$
kapalı diskinin içinde kalan tam sayı koordinatlı \(A,B,C\) üçgenleri incelenir. Alanı
$$\Delta=\frac12$$
olan bu üçgenler arasında çevresi en büyük olan aranır. Birden fazla üçgen aynı çevreye sahipse çevrel çember yarıçapı \(R\) daha büyük olan seçilir ve raporlanan büyüklük
$$T(r)=\frac{R}{r}$$
olur. Doğrudan tarama çok büyük olduğu için çözüm, geometriyi primitif bir taban kenarı ve üçüncü nokta için tek boyutlu bir kafes ailesi üzerinden yeniden kurar.
Bir aday üçgen sabitlenip \(AB\) taban seçilsin. Şöyle yazalım:
$$u=B-A=(a,b),\qquad w=C-A,\qquad L=|u|=\sqrt{a^2+b^2}.$$
Uygulamalar yalnızca seçilen tabanın en uzun kenar olduğu durumları tutar; dolayısıyla
$$|w|\le L,\qquad |u-w|\le L.$$
Kafes noktalarında iki kat alan determinantın mutlak değeridir:
$$2\Delta=|\det(u,w)|.$$
\(\Delta=\frac12\) olduğundan her geçerli üçgen için
$$|\det(u,w)|=1$$
olmalıdır. \(A=(x_A,y_A)\) ve \(C=(x,y)\) yazarsak \(w=C-A\) olur ve koşul
$$a y-b x=a y_A-b x_A\pm1$$
şekline gelir. Buradan \(\gcd(a,b)=1\) olduğu hemen çıkar; aksi halde sol taraf ortak bir bölenin katı olur ve \(\pm1\) veremez.
\(\gcd(a,b)=1\) olduğu için
$$-b x+a y=1$$
lineer Diofant denkleminin tam sayı çözümü vardır. Sağ taraf herhangi bir \(k\) olduğunda, bir özel çözüm bu çözümün \(k\) ile çarpılmasıyla elde edilir. Aynı doğru üzerindeki tüm diğer tam sayı noktalar taban vektörünün tam sayı katları kadar kayar. Böylece tam çözüm ailesi
$$C(t)=C_0+t(a,b),\qquad t\in\mathbb{Z}$$
olur. Yani \(A\), \(B\) ve \(\pm1\) işareti sabitlenince üçüncü nokta ancak tabana paralel tek bir kafes doğrusu üzerinde hareket edebilir.
\(C(t)=C_0+t u\) ifadesini disk koşuluna koyunca
$$|C_0+t u|^2\le r^2$$
elde edilir; bu da
$$L^2 t^2+2(C_0\cdot u)t+\bigl(|C_0|^2-r^2\bigr)\le0$$
ikinci derece eşitsizliğidir. Diskriminant, doğrunun diski kesip kesmediğini söyler. Kesişim varsa geçerli tam sayılar tek bir ardışık aralık oluşturur:
$$t_{\min}\le t\le t_{\max}.$$
Uygulamalar bu sınırları tam sayı tabanlı aşağı-yukarı yuvarlama ile hesaplar; dolayısıyla geometrik uygunluk testi kayan nokta hatasına dayanmaz.
Şunu tanımlayalım:
$$q=u\cdot w.$$
İki vektör de tam sayı koordinatlı olduğu için \(q\) bir tamsayıdır. Lagrange özdeşliğinden
$$|u|^2|w|^2=(u\cdot w)^2+\det(u,w)^2=q^2+1$$
gelir; dolayısıyla
$$|w|=\frac{\sqrt{q^2+1}}{L}.$$
Üçüncü kenar için \(u-w=B-C\) kullanılır. O zaman
$$u\cdot(u-w)=L^2-q,\qquad \det(u,u-w)=\det(u,w),$$
ve böylece
$$|u-w|=\frac{\sqrt{(L^2-q)^2+1}}{L}.$$
Bu yüzden çevre
$$P=L+\frac{\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1}}{L}$$
olur.
Taban en uzun kenar olduğundan hem \(q\) hem de \(L^2-q\) pozitif tam sayıdır. Her \(n\ge1\) için
$$\sqrt{n^2+1}\le n+\frac{1}{2n}$$
eşitsizliği geçerlidir. Bunu bir kez \(q\) için, bir kez de \(L^2-q\) için uygularsak
$$\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1} \le q+\frac{1}{2q}+(L^2-q)+\frac{1}{2(L^2-q)} \le L^2+1$$
elde edilir. \(L\)'ye böldüğümüzde
$$|w|+|u-w|\le L+\frac1L,$$
dolayısıyla da
$$\boxed{P\le2L+\frac1L.}$$
Aramanın temel budama kuralı budur. Bu iyimser üst sınır bile eldeki en iyi çevreden küçük kaldığında daha kısa tabanların sonucu iyileştirmesi imkansızdır.
Disk içindeki herhangi bir kenarın uzunluğu en fazla \(2r\) olabilir. Bu yüzden umut vadeden tabanlar \(2r\)'ye çok yakın olanlardır. Uygulamalar bu farkı
$$d=4r^2-L^2$$
deficiency değeriyle ölçer. Küçük \(d\), neredeyse çap uzunluğunda taban demektir; bu nedenle primitif kenarlar artan deficiency, yani azalan \(L\), sırasıyla işlenir.
Mevcut en iyi çevre \(P^*\) ise yeni bir kenarın kazanabilmesi için
$$2L+\frac1L>P^*$$
olmalıdır. Eşitliğin büyük kökü
$$L_{\min}=\frac{P^*+\sqrt{(P^*)^2-8}}{4}$$
olduğundan \(L<L_{\min}\) olan kenarlar artık gereksizdir. Bu da aramanın yalnızca
$$d_{\max}=4r^2-L_{\min}^2$$
değerine kadar genişlemesinin yeterli olduğu anlamına gelir.
Şunu alalım:
$$A=(0,0),\qquad B=(2,1).$$
Bu durumda \(u=(2,1)\) ve \(L^2=5\) olur. Alan koşulu
$$|\det(u,C-A)|=|2y-x|=1$$
şeklindedir. \(+1\) dalını seçersek \(2y-x=1\) doğrusunu elde ederiz. Bu doğru üzerindeki bir tam sayı nokta \((-1,0)\) olduğundan tüm çözümler
$$C(t)=(-1,0)+t(2,1)$$
olur. Yarıçapı \(3\) olan disk içinde kalmak için
$$(-1+2t)^2+t^2\le9$$
gereklidir ve buradan \(t=0,1\) çıkar. \(t=1\) seçimi \(C=(1,1)\) verir. Sonra
$$|C-A|^2=2,\qquad |C-B|^2=1,\qquad P=\sqrt5+\sqrt2+1$$
olur. \(\Delta=\frac12\) olduğundan çevrel çember yarıçapı
$$R=\frac{|AB|\cdot|AC|\cdot|BC|}{4\Delta} =\frac{\sqrt5\cdot\sqrt2\cdot1}{2} =\frac{\sqrt{10}}{2}$$
şeklindedir.
Uygulama önce her tam sayı \(x\in[-r,r]\) için disk içinde kalabilen en büyük \(|y|\) değerini önceden hesaplar. Böylece kaydırılmış bir taban kenarının iki ucunun da çember içinde olup olmadığı hızlıca test edilir.
Daha sonra \(1\le b\le a\) koşuluyla primitif kenar vektörleri \((a,b)\) üretilir; böylece dönme ve yansıma simetrileri tekrar sayılmaz. Yalnızca mevcut deficiency penceresine düşen uzunluk kareleri tutulur ve bunlar uzun kenardan kısa kenara doğru işlenir.
Her geçerli taban yerleşimi için C++, Python ve Java uygulamaları, alanın \(+\frac12\) ve \(-\frac12\) olmasına karşılık gelen iki determinant doğrusunu inceler. Seçilen doğru üzerinde bir tam sayı nokta, genişletilmiş Öklid algoritmasıyla kurulur; ardından bu nokta taban yönünde kaydırılarak disk testini veren ikinci derece ifade küçük ve tam sayı kalacak biçimde merkezlenir.
Elde edilen \(t\)-aralığındaki her tam sayı nokta denenir. Üçüncü noktanın bir uç noktaya çakıştığı veya diğer iki kenardan birinin tabandan uzun olduğu durumlar elenir. Kalan adaylar önce çevreye, eşitlikte ise çevrel çember yarıçapına göre karşılaştırılır.
C++ sürümü kenarları batch'ler halinde paralel işler, Java sürümü aynı tam aramayı kritik yerlerde büyük tamsayı aritmetiğiyle yansıtır ve Python sürümü yerel hesaplamayı başlatıp son sayısal çıktıyı ayıklayan ince bir köprü görevi görür.
\(E(D)\), deficiency değeri en çok \(D\) olan primitif kenar vektörlerinin sayısı olsun. Disk sınır tablosunu hazırlamak \(O(r)\) zaman ve \(O(r)\) bellek ister. Güncel aday kenarları üretip sıralamak \(O(E(D)\log E(D))\) maliyetlidir.
Tek bir kenar için çözücü, iki ucun da disk içinde kaldığı bütün kaydırmaları gezer; en kötü durumda bu \(O(r^2)\) olabilir. Her geçerli kaydırma en fazla iki determinant doğrusu üretir ve her doğru üçüncü nokta için tek bir ardışık tam sayı aralığı verir. Bu yüzden bir arama turu için kasıtlı olarak gevşek üst sınır \(O(r^2E(D))\)'dir. Pratikte ise deficiency penceresi küçük kalır, çevre üst sınırı birçok kenarı erkenden eler ve \(t\)-aralıkları genellikle kısadır.
Sonuç olarak çalışma süresi veri bağımlıdır; buna karşılık bellek kullanımı \(O(r+E(D))\) mertebesindedir. Paralel C++ sürümünde buna yalnızca iş parçacığına özel küçük durumlar eklenir.
Se estudian triángulos de coordenadas enteras \(A,B,C\) cuyas tres esquinas están dentro del disco cerrado
$$x^2+y^2\le r^2.$$
Entre todos los triángulos de ese tipo con área
$$\Delta=\frac12,$$
hay que maximizar el perímetro. Si varios triángulos alcanzan el mismo perímetro, se prefiere el de mayor circunradio \(R\), y la cantidad reportada es
$$T(r)=\frac{R}{r}.$$
La búsqueda directa es inmensa, así que la solución reorganiza el problema en torno a una arista base primitiva y a una familia unidimensional de puntos enteros para el tercer vértice.
Fijemos un triángulo candidato y tomemos \(AB\) como base. Escribimos
$$u=B-A=(a,b),\qquad w=C-A,\qquad L=|u|=\sqrt{a^2+b^2}.$$
Las implementaciones solo conservan las configuraciones en las que la base elegida es el lado más largo, de modo que
$$|w|\le L,\qquad |u-w|\le L.$$
Para puntos de la red, el doble del área es el valor absoluto del determinante:
$$2\Delta=|\det(u,w)|.$$
Como \(\Delta=\frac12\), todo triángulo admisible cumple
$$|\det(u,w)|=1.$$
Si \(A=(x_A,y_A)\) y \(C=(x,y)\), entonces \(w=C-A\), así que la misma condición puede escribirse como
$$a y-b x=a y_A-b x_A\pm1.$$
Esto obliga a que \(\gcd(a,b)=1\); si \(a\) y \(b\) tuvieran un divisor común mayor que \(1\), el lado izquierdo siempre sería múltiplo de ese divisor y nunca podría valer \(\pm1\).
Como \(\gcd(a,b)=1\), la ecuación diofántica lineal
$$-b x+a y=1$$
tiene una solución entera. Si el lado derecho deseado es un entero \(k\), basta multiplicar esa solución por \(k\) para obtener un punto particular. Todos los demás puntos enteros sobre la misma recta difieren en un múltiplo entero del vector base \(u\), de modo que la familia completa es
$$C(t)=C_0+t(a,b),\qquad t\in\mathbb{Z}.$$
Por tanto, una vez fijados \(A\), \(B\) y el signo \(\pm1\), el tercer vértice solo puede moverse sobre una recta de la red paralela a la base.
Al sustituir \(C(t)=C_0+t u\) en la restricción del disco se obtiene
$$|C_0+t u|^2\le r^2,$$
que se expande como la desigualdad cuadrática
$$L^2 t^2+2(C_0\cdot u)t+\bigl(|C_0|^2-r^2\bigr)\le0.$$
El discriminante indica si la recta corta el disco. Cuando sí lo hace, los enteros admisibles forman un único intervalo contiguo
$$t_{\min}\le t\le t_{\max}.$$
Las implementaciones calculan estos extremos con divisiones enteras exactas, usando piso y techo, así que la prueba geométrica de viabilidad no depende de redondeos de punto flotante.
Definimos
$$q=u\cdot w.$$
Este valor es entero porque ambos vectores tienen coordenadas enteras. La identidad de Lagrange da
$$|u|^2|w|^2=(u\cdot w)^2+\det(u,w)^2=q^2+1,$$
de donde
$$|w|=\frac{\sqrt{q^2+1}}{L}.$$
Para el tercer lado usamos \(u-w=B-C\). Entonces
$$u\cdot(u-w)=L^2-q,\qquad \det(u,u-w)=\det(u,w),$$
y por tanto
$$|u-w|=\frac{\sqrt{(L^2-q)^2+1}}{L}.$$
Así, el perímetro toma la forma
$$P=L+\frac{\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1}}{L}.$$
Como la base elegida debe ser el lado más largo, tanto \(q\) como \(L^2-q\) son enteros positivos. Para cualquier entero \(n\ge1\), se cumple
$$\sqrt{n^2+1}\le n+\frac{1}{2n}.$$
Aplicando esta desigualdad a \(q\) y a \(L^2-q\), obtenemos
$$\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1} \le q+\frac{1}{2q}+(L^2-q)+\frac{1}{2(L^2-q)} \le L^2+1.$$
Al dividir entre \(L\), resulta
$$|w|+|u-w|\le L+\frac1L,$$
y por consiguiente
$$\boxed{P\le2L+\frac1L.}$$
Esta es la desigualdad central para la poda. Cuando incluso este valor optimista ya queda por debajo del mejor perímetro encontrado, ninguna base más corta puede mejorar la respuesta.
Cualquier arista contenida en el disco tiene longitud a lo sumo \(2r\). Por eso las bases más prometedoras son las que tienen \(L\) muy cerca de \(2r\). Las implementaciones miden esa distancia mediante la deficiencia
$$d=4r^2-L^2.$$
Un valor pequeño de \(d\) significa una base casi diametral, así que las aristas primitivas se generan en orden creciente de deficiencia, o equivalentemente en orden decreciente de \(L\).
Si el mejor perímetro actual es \(P^*\), una arista futura solo puede ganar si
$$2L+\frac1L>P^*.$$
La raíz mayor de la igualdad correspondiente es
$$L_{\min}=\frac{P^*+\sqrt{(P^*)^2-8}}{4}.$$
Por tanto, ninguna arista con \(L<L_{\min}\) importa, y la búsqueda solo debe cubrir deficiencias hasta
$$d_{\max}=4r^2-L_{\min}^2.$$
Tomemos
$$A=(0,0),\qquad B=(2,1).$$
Entonces \(u=(2,1)\) y \(L^2=5\). La condición de área se convierte en
$$|\det(u,C-A)|=|2y-x|=1.$$
Si elegimos la rama \(+1\), obtenemos la recta \(2y-x=1\). Un punto entero sobre ella es \((-1,0)\), así que todas las soluciones son
$$C(t)=(-1,0)+t(2,1).$$
Para quedar dentro del disco de radio \(3\), necesitamos
$$(-1+2t)^2+t^2\le9,$$
lo que deja \(t=0\) y \(t=1\). El valor \(t=1\) produce \(C=(1,1)\), y entonces
$$|C-A|^2=2,\qquad |C-B|^2=1,\qquad P=\sqrt5+\sqrt2+1.$$
Como \(\Delta=\frac12\), el circunradio es
$$R=\frac{|AB|\cdot|AC|\cdot|BC|}{4\Delta} =\frac{\sqrt5\cdot\sqrt2\cdot1}{2} =\frac{\sqrt{10}}{2}.$$
La implementación precomputa primero, para cada entero \(x\in[-r,r]\), la altura máxima \(|y|\) que sigue dentro del disco. Eso permite verificar rápidamente si los dos extremos de una base trasladada siguen dentro del círculo.
Después construye vectores de arista primitivos \((a,b)\) con \(1\le b\le a\), evitando repetir simetrías de rotación y reflexión. Solo se conservan los vectores cuyo cuadrado de longitud cae en la ventana actual de deficiencia, y se procesan desde las aristas más largas hacia las más cortas.
Para cada traslado válido de la base, las implementaciones en C++, Python y Java examinan las dos rectas determinantes que corresponden a área \(+\frac12\) y \(-\frac12\). Un punto entero sobre la recta elegida se obtiene con el algoritmo extendido de Euclides y luego se desplaza a lo largo de la dirección de la base para mantener pequeña y exacta la desigualdad cuadrática del disco.
Se inspecciona cada punto entero del intervalo resultante de \(t\). La implementación descarta los casos en los que el tercer punto coincide con un extremo o en los que uno de los otros lados supera la longitud de la base. Los candidatos restantes se comparan primero por perímetro y, en caso de empate, por circunradio.
La versión en C++ procesa lotes de aristas en paralelo, la versión en Java reproduce la misma búsqueda exacta usando aritmética de enteros grandes cuando hace falta, y la versión en Python es un puente ligero que lanza el cálculo nativo y extrae la respuesta numérica final.
Sea \(E(D)\) el número de vectores de arista primitivos cuya deficiencia es como mucho \(D\). Precomputar la tabla del borde del disco cuesta \(O(r)\) tiempo y \(O(r)\) memoria. Generar y ordenar las aristas candidatas actuales cuesta \(O(E(D)\log E(D))\).
Para una arista concreta, el solucionador recorre todos los traslados que mantienen ambos extremos dentro del disco; en el peor caso eso puede llegar a \(O(r^2)\). Cada traslado válido produce como máximo dos rectas determinantes, y cada recta aporta un único intervalo contiguo de enteros para el tercer vértice. Una cota deliberadamente holgada para una ronda de búsqueda es por tanto \(O(r^2E(D))\), aunque en la práctica es mucho menor porque la ventana de deficiencia se mantiene pequeña, la cota del perímetro elimina muchas aristas pronto y el intervalo de \(t\) suele ser corto.
En conjunto, el tiempo es muy dependiente de los datos, mientras que la memoria sigue siendo moderada: \(O(r+E(D))\), más el pequeño estado local por hilo en la versión paralela de C++.
我们研究的是顶点都落在闭圆盘
$$x^2+y^2\le r^2$$
中的整数点三角形 \(A,B,C\)。在所有面积满足
$$\Delta=\frac12$$
的这类三角形里，目标是让周长最大。如果有多个三角形达到同样的最大周长，就取外接圆半径 \(R\) 更大的那个，最后输出
$$T(r)=\frac{R}{r}.$$
直接枚举所有三角形的规模过于庞大，所以解法把问题改写成“先选一条原始底边，再在一条整数直线族上寻找第三个点”。
固定一个候选三角形，并把 \(AB\) 选作底边。记
$$u=B-A=(a,b),\qquad w=C-A,\qquad L=|u|=\sqrt{a^2+b^2}.$$
实现中只保留“所选底边确实是最长边”的情况，因此有
$$|w|\le L,\qquad |u-w|\le L.$$
对整数点三角形来说，两倍面积就是行列式的绝对值：
$$2\Delta=|\det(u,w)|.$$
由于这里
$$\Delta=\frac12,$$
所以每个合法三角形都必须满足
$$|\det(u,w)|=1.$$
如果写 \(A=(x_A,y_A)\)、\(C=(x,y)\)，那么 \(w=C-A\)，于是同一个条件等价于
$$a y-b x=a y_A-b x_A\pm1.$$
这一步已经说明 \((a,b)\) 必须是原始向量，也就是 \(\gcd(a,b)=1\)。否则左边始终会被某个大于 \(1\) 的公因子整除，不可能得到 \(\pm1\)。
既然 \(\gcd(a,b)=1\)，线性丢番图方程
$$-b x+a y=1$$
一定存在整数解。若目标右端是某个整数 \(k\)，把这组解整体乘以 \(k\) 就得到该直线上的一个整数点。直线上其他整数点只会沿着底边方向平移整数倍，因此全部解可以统一写成
$$C(t)=C_0+t(a,b),\qquad t\in\mathbb{Z}.$$
也就是说，一旦 \(A\)、\(B\) 以及 \(\pm1\) 的符号固定下来，第三个顶点就只能落在一条与底边平行的整数直线上。
把 \(C(t)=C_0+t u\) 代入圆盘约束，就得到
$$|C_0+t u|^2\le r^2,$$
展开后是二次不等式
$$L^2 t^2+2(C_0\cdot u)t+\bigl(|C_0|^2-r^2\bigr)\le0.$$
判别式决定这条直线是否真的与圆盘相交。只要相交，合法的整数参数 \(t\) 就会形成一个连续区间
$$t_{\min}\le t\le t_{\max}.$$
实现中用的是精确的整数下取整与上取整运算，所以这一几何可行性判断不依赖浮点近似。
定义
$$q=u\cdot w.$$
因为 \(u\) 和 \(w\) 都是整数向量，所以 \(q\) 是整数。利用拉格朗日恒等式有
$$|u|^2|w|^2=(u\cdot w)^2+\det(u,w)^2=q^2+1,$$
于是得到
$$|w|=\frac{\sqrt{q^2+1}}{L}.$$
对第三条边，注意 \(u-w=B-C\)。于是
$$u\cdot(u-w)=L^2-q,\qquad \det(u,u-w)=\det(u,w),$$
从而
$$|u-w|=\frac{\sqrt{(L^2-q)^2+1}}{L}.$$
因此周长可以写成
$$P=L+\frac{\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1}}{L}.$$
由于实现要求所选底边是最长边，所以 \(q\) 与 \(L^2-q\) 都必须是正整数。对任意整数 \(n\ge1\)，都有
$$\sqrt{n^2+1}\le n+\frac{1}{2n}.$$
把这个不等式分别应用到 \(q\) 和 \(L^2-q\) 上，就有
$$\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1} \le q+\frac{1}{2q}+(L^2-q)+\frac{1}{2(L^2-q)} \le L^2+1.$$
再除以 \(L\)，得到
$$|w|+|u-w|\le L+\frac1L,$$
于是
$$\boxed{P\le2L+\frac1L.}$$
这就是搜索中的核心剪枝条件。只要连这个乐观上界都已经不如当前最好周长，那么更短的底边就可以安全地全部跳过。
圆盘内任意一条边的长度都不会超过 \(2r\)。因此最有希望成为最优解的底边，应该让 \(L\) 尽量接近 \(2r\)。实现里把这种“离直径还差多少”写成
$$d=4r^2-L^2.$$
\(d\) 越小，底边越接近直径长度。所以候选原始边向量是按亏量递增、也就是按 \(L\) 递减的顺序处理的。
如果当前最优周长是 \(P^*\)，那么未来某条边还能超越它的必要条件是
$$2L+\frac1L>P^*.$$
解对应的等式，可以得到较大的那个根
$$L_{\min}=\frac{P^*+\sqrt{(P^*)^2-8}}{4}.$$
因此所有 \(L<L_{\min}\) 的边都不可能改写答案，搜索只需要扩展到
$$d_{\max}=4r^2-L_{\min}^2$$
为止。
取
$$A=(0,0),\qquad B=(2,1).$$
这时 \(u=(2,1)\)，并且 \(L^2=5\)。面积条件变成
$$|\det(u,C-A)|=|2y-x|=1.$$
若选择 \(+1\) 这一支，对应直线是 \(2y-x=1\)。这条直线上一个整数点是 \((-1,0)\)，所以全部整数解都可写为
$$C(t)=(-1,0)+t(2,1).$$
若要求点 \(C\) 落在半径为 \(3\) 的圆盘里，就必须满足
$$(-1+2t)^2+t^2\le9,$$
因此只剩 \(t=0\) 和 \(t=1\)。取 \(t=1\) 时，\(C=(1,1)\)。于是
$$|C-A|^2=2,\qquad |C-B|^2=1,\qquad P=\sqrt5+\sqrt2+1.$$
又因为 \(\Delta=\frac12\)，外接圆半径为
$$R=\frac{|AB|\cdot|AC|\cdot|BC|}{4\Delta} =\frac{\sqrt5\cdot\sqrt2\cdot1}{2} =\frac{\sqrt{10}}{2}.$$
实现首先会为每个整数 \(x\in[-r,r]\) 预计算在圆盘内部仍然允许的最大 \(|y|\)。这样一来，底边平移到某个位置之后，只需查表就能快速判断两个端点是否还在圆内。
接着，它生成满足 \(1\le b\le a\) 的原始边向量 \((a,b)\)，避免重复遍历旋转与镜像对称情形。只有长度平方落在当前亏量窗口里的向量才会被保留，而且处理顺序是从长边到短边。
对每一个可行的底边平移位置，C++、Python 和 Java 实现都会考察面积为 \(+\frac12\) 与 \(-\frac12\) 的两条行列式直线。程序先用扩展欧几里得算法在目标直线上构造一个整数点，再沿底边方向把它平移到更靠近原点的位置，从而让后续的二次圆盘判定既精确又数值稳定。
随后枚举由此得到的整数 \(t\) 区间。若第三个点与底边端点重合，或者另外两条边中有一条长于底边，就直接丢弃。剩余候选先比较周长，若周长相同，再比较外接圆半径。
C++ 版本把边按批次并行处理；Java 版本在需要的地方使用大整数，复现同样的精确搜索；Python 版本则是一个很薄的桥接层，负责启动本地计算并解析最终的数值输出。
记 \(E(D)\) 为亏量不超过 \(D\) 的原始边向量个数。预计算圆盘边界表需要 \(O(r)\) 时间和 \(O(r)\) 内存。生成并排序当前候选边需要 \(O(E(D)\log E(D))\)。
对单条边而言，求解器会扫描所有使得两个端点仍在圆盘中的平移位置；在最坏情况下，这部分可以达到 \(O(r^2)\)。每个有效平移最多产生两条行列式直线，而每条直线只对应一个连续的整数参数区间。因此，一轮搜索的宽松上界可以写成 \(O(r^2E(D))\)。实际运行通常远小于这个值，因为亏量窗口一般不大，周长上界会提前筛掉很多边，而且整数 \(t\) 区间往往很短。
总体来说，这个方法的运行时间高度依赖数据，但空间仍然比较克制，为 \(O(r+E(D))\)。并行的 C++ 版本只额外使用少量线程局部状态。
Рассматриваются треугольники \(A,B,C\) с целочисленными координатами, чьи вершины лежат в замкнутом диске
$$x^2+y^2\le r^2.$$
Среди всех таких треугольников площади
$$\Delta=\frac12$$
нужно найти треугольник с максимальным периметром. Если несколько треугольников дают один и тот же периметр, выбирается тот, у которого больше радиус описанной окружности \(R\), а итоговая величина равна
$$T(r)=\frac{R}{r}.$$
Полный перебор слишком велик, поэтому решение перестраивает задачу через примитивное базовое ребро и одномерное семейство решеточных положений для третьей вершины.
Зафиксируем кандидат и выберем сторону \(AB\) в качестве базы. Обозначим
$$u=B-A=(a,b),\qquad w=C-A,\qquad L=|u|=\sqrt{a^2+b^2}.$$
В реализации сохраняются только те конфигурации, где выбранная база является самой длинной стороной, то есть
$$|w|\le L,\qquad |u-w|\le L.$$
Для решеточного треугольника удвоенная площадь равна модулю определителя:
$$2\Delta=|\det(u,w)|.$$
Так как
$$\Delta=\frac12,$$
каждый допустимый треугольник должен удовлетворять условию
$$|\det(u,w)|=1.$$
Если \(A=(x_A,y_A)\), \(C=(x,y)\), то \(w=C-A\), и то же самое условие принимает вид
$$a y-b x=a y_A-b x_A\pm1.$$
Отсюда сразу следует \(\gcd(a,b)=1\): если бы у \(a\) и \(b\) был общий делитель больше \(1\), левая часть всегда делилась бы на него и не могла бы равняться \(\pm1\).
Поскольку \(\gcd(a,b)=1\), линейное диофантово уравнение
$$-b x+a y=1$$
имеет целочисленное решение. Если нужная правая часть равна некоторому целому \(k\), то частное решение получается умножением на \(k\). Все остальные целые точки на той же прямой отличаются на целое кратное вектора базы \(u\), так что полное семейство имеет вид
$$C(t)=C_0+t(a,b),\qquad t\in\mathbb{Z}.$$
Значит, при фиксированных \(A\), \(B\) и выборе знака \(\pm1\) третья вершина может двигаться только вдоль одной решеточной прямой, параллельной базе.
Подставляя \(C(t)=C_0+t u\) в ограничение диска, получаем
$$|C_0+t u|^2\le r^2,$$
то есть квадратное неравенство
$$L^2 t^2+2(C_0\cdot u)t+\bigl(|C_0|^2-r^2\bigr)\le0.$$
Дискриминант показывает, пересекает ли эта прямая диск вообще. Если пересекает, допустимые целые значения \(t\) образуют один непрерывный интервал
$$t_{\min}\le t\le t_{\max}.$$
Границы интервала вычисляются точно с помощью целочисленных операций пола и потолка, поэтому геометрическая проверка не опирается на неточные вещественные округления.
Определим
$$q=u\cdot w.$$
Это целое число, потому что оба вектора целочисленные. По тождеству Лагранжа
$$|u|^2|w|^2=(u\cdot w)^2+\det(u,w)^2=q^2+1,$$
следовательно,
$$|w|=\frac{\sqrt{q^2+1}}{L}.$$
Для третьей стороны используем \(u-w=B-C\). Тогда
$$u\cdot(u-w)=L^2-q,\qquad \det(u,u-w)=\det(u,w),$$
и потому
$$|u-w|=\frac{\sqrt{(L^2-q)^2+1}}{L}.$$
Итак, периметр равен
$$P=L+\frac{\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1}}{L}.$$
Так как база обязана быть самой длинной стороной, числа \(q\) и \(L^2-q\) являются положительными целыми. Для любого целого \(n\ge1\) верно
$$\sqrt{n^2+1}\le n+\frac{1}{2n}.$$
Применяя это неравенство к \(q\) и \(L^2-q\), получаем
$$\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1} \le q+\frac{1}{2q}+(L^2-q)+\frac{1}{2(L^2-q)} \le L^2+1.$$
После деления на \(L\) имеем
$$|w|+|u-w|\le L+\frac1L,$$
а значит,
$$\boxed{P\le2L+\frac1L.}$$
Это и есть основная оценка для pruning. Если даже такой оптимистичный верхний предел уже хуже текущего лучшего периметра, более короткие базы можно отбросить без риска.
Любое ребро внутри диска имеет длину не больше \(2r\). Поэтому перспективные базы должны иметь \(L\), близкое к \(2r\). Реализация измеряет этот зазор дефицитом
$$d=4r^2-L^2.$$
Малый \(d\) означает почти диаметральную базу, поэтому примитивные ребра перебираются в порядке возрастания дефицита, то есть убывания \(L\).
Если текущий лучший периметр равен \(P^*\), то новое ребро может улучшить ответ только при условии
$$2L+\frac1L>P^*.$$
Больший корень соответствующего уравнения равен
$$L_{\min}=\frac{P^*+\sqrt{(P^*)^2-8}}{4}.$$
Следовательно, все ребра с \(L<L_{\min}\) уже бесполезны, и поиск нужно расширять лишь до дефицита
$$d_{\max}=4r^2-L_{\min}^2.$$
Возьмем
$$A=(0,0),\qquad B=(2,1).$$
Тогда \(u=(2,1)\), а \(L^2=5\). Условие на площадь принимает вид
$$|\det(u,C-A)|=|2y-x|=1.$$
Если выбрать ветвь \(+1\), получаем прямую \(2y-x=1\). Одна целая точка на ней равна \((-1,0)\), поэтому все решения записываются как
$$C(t)=(-1,0)+t(2,1).$$
Чтобы точка лежала в диске радиуса \(3\), нужно
$$(-1+2t)^2+t^2\le9,$$
откуда остаются \(t=0\) и \(t=1\). При \(t=1\) получаем \(C=(1,1)\), после чего
$$|C-A|^2=2,\qquad |C-B|^2=1,\qquad P=\sqrt5+\sqrt2+1.$$
Поскольку \(\Delta=\frac12\), радиус описанной окружности равен
$$R=\frac{|AB|\cdot|AC|\cdot|BC|}{4\Delta} =\frac{\sqrt5\cdot\sqrt2\cdot1}{2} =\frac{\sqrt{10}}{2}.$$
Сначала реализация предварительно вычисляет для каждого целого \(x\in[-r,r]\) максимально возможное \(|y|\), которое все еще остается внутри диска. Это позволяет быстро проверять, остаются ли обе вершины сдвинутой базовой стороны внутри окружности.
Затем строятся примитивные векторы ребра \((a,b)\) с условием \(1\le b\le a\), чтобы не пересчитывать симметрии поворота и отражения. Сохраняются только те векторы, чья длина попадает в текущее окно дефицита, и обрабатываются они от более длинных к более коротким.
Для каждого допустимого сдвига базы реализации на C++, Python и Java рассматривают две прямые определителя, соответствующие площади \(+\frac12\) и \(-\frac12\). Целая точка на нужной прямой строится расширенным алгоритмом Евклида, а затем сдвигается вдоль направления базы так, чтобы квадратное неравенство диска оставалось компактным и точным.
После этого проверяется каждая целая точка в полученном интервале параметра \(t\). Случаи, где третья вершина совпадает с концом базы или одна из двух других сторон длиннее базы, отбрасываются. Оставшиеся кандидаты сравниваются сначала по периметру, а при равенстве по радиусу описанной окружности.
Версия на C++ обрабатывает пачки ребер параллельно, версия на Java воспроизводит тот же точный поиск с использованием больших целых там, где это необходимо, а версия на Python служит тонким мостом: она запускает нативное вычисление и извлекает итоговый числовой результат.
Пусть \(E(D)\) обозначает число примитивных векторов ребра с дефицитом не больше \(D\). Предварительное построение таблицы границы диска стоит \(O(r)\) времени и \(O(r)\) памяти. Генерация и сортировка текущих кандидатных ребер требует \(O(E(D)\log E(D))\).
Для одного ребра решатель перебирает все сдвиги, при которых оба конца остаются внутри диска; в худшем случае это может достигать \(O(r^2)\). Каждый допустимый сдвиг порождает не более двух прямых определителя, а каждая такая прямая дает один непрерывный интервал целых параметров третьей вершины. Поэтому заведомо грубая оценка для одного раунда поиска равна \(O(r^2E(D))\). На практике она заметно меньше, потому что окно дефицита остается небольшим, оценка периметра рано отсекает многие ребра, а интервалы по \(t\) обычно короткие.
Итак, время работы сильно зависит от данных, а память остается умеренной: \(O(r+E(D))\), плюс небольшой потоковый локальный контекст в параллельной версии на C++.
نبحث في المثلثات \(A,B,C\) ذات الإحداثيات الصحيحة التي تقع رؤوسها داخل القرص المغلق
$$x^2+y^2\le r^2.$$
ومن بين جميع هذه المثلثات التي مساحتها
$$\Delta=\frac12,$$
نريد تعظيم المحيط. وإذا وُجد أكثر من مثلث يحقق المحيط نفسه، نختار المثلث ذي نصف قطر الدائرة المحيطة \(R\) الأكبر، ثم نُخرج الكمية
$$T(r)=\frac{R}{r}.$$
العد المباشر غير عملي، لذلك تعيد الحلول صياغة المسألة عبر ضلع قاعدة أولي، ثم عائلة أحادية البعد من النقاط الصحيحة المحتملة للرأس الثالث.
لنثبت مثلثًا مرشحًا ونختَر الضلع \(AB\) بوصفه القاعدة. نكتب
$$u=B-A=(a,b),\qquad w=C-A,\qquad L=|u|=\sqrt{a^2+b^2}.$$
التنفيذ لا يحتفظ إلا بالحالات التي تكون فيها القاعدة المختارة هي الضلع الأطول، ولذلك
$$|w|\le L,\qquad |u-w|\le L.$$
في حالة نقاط الشبكة، يساوي ضعف المساحة القيمة المطلقة للمحدد:
$$2\Delta=|\det(u,w)|.$$
وبما أن
$$\Delta=\frac12,$$
فإن كل مثلث صالح يجب أن يحقق
$$|\det(u,w)|=1.$$
إذا كتبنا \(A=(x_A,y_A)\) و\(C=(x,y)\)، فإن \(w=C-A\)، وعندئذ يصبح الشرط
$$a y-b x=a y_A-b x_A\pm1.$$
وهذا يفرض مباشرةً أن \(\gcd(a,b)=1\). فلو كان لـ \(a\) و\(b\) قاسم مشترك أكبر من \(1\)، لكانت الجهة اليسرى دائمًا مضاعفًا لذلك القاسم، ومن المستحيل أن تساوي \(\pm1\).
بما أن \(\gcd(a,b)=1\)، فإن المعادلة الديوفانتية الخطية
$$-b x+a y=1$$
لها حل صحيح. وإذا كان الطرف الأيمن المطلوب عددًا صحيحًا \(k\)، فإن ضرب ذلك الحل في \(k\) يعطينا نقطة صحيحة واحدة على الخط المطلوب. وكل نقطة صحيحة أخرى على الخط نفسه تختلف بمضاعف صحيح لمتجه القاعدة \(u\)، ولذلك فإن العائلة الكاملة هي
$$C(t)=C_0+t(a,b),\qquad t\in\mathbb{Z}.$$
إذن، بعد تثبيت \(A\) و\(B\) واختيار الإشارة \(\pm1\)، لا يمكن للرأس الثالث إلا أن يتحرك على خط شبكي واحد موازٍ للقاعدة.
بالتعويض عن \(C(t)=C_0+t u\) في شرط القرص نحصل على
$$|C_0+t u|^2\le r^2,$$
وهو ما يتمدد إلى المتراجحة التربيعية
$$L^2 t^2+2(C_0\cdot u)t+\bigl(|C_0|^2-r^2\bigr)\le0.$$
يقرر المميز ما إذا كان الخط يقطع القرص أصلًا. وإذا حدث التقاطع، فإن قيم \(t\) الصحيحة المسموح بها تشكل فترة متصلة واحدة
$$t_{\min}\le t\le t_{\max}.$$
ويحسب التنفيذ هذين الحدين بحسابات صحيحة دقيقة باستخدام التقريب لأعلى ولأسفل، لذلك لا تعتمد صلاحية النقطة على تقريب عشري عائم.
لنعرّف
$$q=u\cdot w.$$
هذا عدد صحيح لأن كلا المتجهين صحيحا الإحداثيات. ومن هوية لاغرانج نحصل على
$$|u|^2|w|^2=(u\cdot w)^2+\det(u,w)^2=q^2+1,$$
ومنها
$$|w|=\frac{\sqrt{q^2+1}}{L}.$$
أما بالنسبة للضلع الثالث فنستخدم \(u-w=B-C\). عندئذ
$$u\cdot(u-w)=L^2-q,\qquad \det(u,u-w)=\det(u,w),$$
وبالتالي
$$|u-w|=\frac{\sqrt{(L^2-q)^2+1}}{L}.$$
إذن يصبح المحيط
$$P=L+\frac{\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1}}{L}.$$
بما أن القاعدة المختارة يجب أن تكون الضلع الأطول، فإن \(q\) و\(L^2-q\) عددان صحيحان موجبان. ولكل عدد صحيح \(n\ge1\) لدينا
$$\sqrt{n^2+1}\le n+\frac{1}{2n}.$$
وعند تطبيق ذلك مرة على \(q\) ومرة على \(L^2-q\)، نحصل على
$$\sqrt{q^2+1}+\sqrt{(L^2-q)^2+1} \le q+\frac{1}{2q}+(L^2-q)+\frac{1}{2(L^2-q)} \le L^2+1.$$
وبالقسمة على \(L\) ينتج
$$|w|+|u-w|\le L+\frac1L,$$
ومن ثم
$$\boxed{P\le2L+\frac1L.}$$
هذه هي المتراجحة الأساسية المستخدمة في التقليم. فإذا كان هذا الحد المتفائل نفسه أقل من أفضل محيط تم إيجاده حتى الآن، فلا يمكن لأي قاعدة أقصر أن تحسن النتيجة.
أي ضلع داخل القرص لا يمكن أن يتجاوز طوله \(2r\). لذلك فإن الأضلاع القاعدية الواعدة هي التي يكون فيها \(L\) قريبًا جدًا من \(2r\). وتقيس الحلول هذا الابتعاد بالكمية
$$d=4r^2-L^2.$$
كلما كان \(d\) صغيرًا كانت القاعدة أقرب إلى القطر. ولهذا تُولَّد الأضلاع الأولية بترتيب متزايد في \(d\)، أي بترتيب تنازلي في \(L\).
إذا كان أفضل محيط حاليًا هو \(P^*\)، فإن أي ضلع لاحق لا يمكنه الفوز إلا إذا تحقق
$$2L+\frac1L>P^*.$$
والجذر الأكبر للمعادلة المقابلة هو
$$L_{\min}=\frac{P^*+\sqrt{(P^*)^2-8}}{4}.$$
إذًا كل ضلع يحقق \(L<L_{\min}\) يصبح غير مهم، ولا حاجة لتوسيع البحث إلا حتى
$$d_{\max}=4r^2-L_{\min}^2.$$
خذ
$$A=(0,0),\qquad B=(2,1).$$
عندئذ \(u=(2,1)\) و\(L^2=5\). يصبح شرط المساحة
$$|\det(u,C-A)|=|2y-x|=1.$$
إذا اخترنا فرع \(+1\)، نحصل على الخط \(2y-x=1\). توجد عليه النقطة الصحيحة \((-1,0)\)، ولذلك تكون جميع الحلول
$$C(t)=(-1,0)+t(2,1).$$
ولكي تبقى النقطة \(C\) داخل قرص نصف قطره \(3\)، يجب أن يتحقق
$$(-1+2t)^2+t^2\le9,$$
ومن ثم نحصل على \(t=0\) و\(t=1\). عند اختيار \(t=1\) نحصل على \(C=(1,1)\)، وبعدها
$$|C-A|^2=2,\qquad |C-B|^2=1,\qquad P=\sqrt5+\sqrt2+1.$$
وبما أن \(\Delta=\frac12\)، فإن نصف قطر الدائرة المحيطة يساوي
$$R=\frac{|AB|\cdot|AC|\cdot|BC|}{4\Delta} =\frac{\sqrt5\cdot\sqrt2\cdot1}{2} =\frac{\sqrt{10}}{2}.$$
يبدأ التنفيذ بحساب القيمة العظمى لـ \(|y|\) المسموح بها داخل القرص لكل عدد صحيح \(x\in[-r,r]\). وهذا يجعل اختبار بقاء طرفي القاعدة المزاحة داخل الدائرة سريعًا جدًا.
بعد ذلك يبني متجهات أضلاع أولية \((a,b)\) مع الشرط \(1\le b\le a\)، حتى لا يعيد عدّ الحالات المتناظرة بالدوران أو الانعكاس. ولا تُحفظ إلا المتجهات التي يقع مربع طولها داخل نافذة النقص الحالية، ثم تُعالج من الأضلاع الأطول إلى الأقصر.
لكل إزاحة صالحة للقاعدة، تفحص تطبيقات C++ وPython وJava خطي المحدد الموافقين للمساحة \(+\frac12\) و\(-\frac12\). وتُبنى نقطة صحيحة على الخط المختار بواسطة خوارزمية إقليدس الموسعة، ثم تُزاح على طول اتجاه القاعدة من أجل إبقاء متراجحة القرص التربيعية صغيرة ودقيقة في الوقت نفسه.
بعد ذلك تُفحص كل نقطة صحيحة في مجال \(t\) الناتج. وتُرفض الحالات التي يتطابق فيها الرأس الثالث مع أحد طرفي القاعدة أو التي يكون فيها أحد الضلعين الآخرين أطول من القاعدة. أما المرشحون الباقون فيُقارنون أولًا بالمحيط، وعند التعادل يُستخدم نصف قطر الدائرة المحيطة لكسر التعادل.
نسخة C++ تعالج دفعات من الأضلاع بالتوازي، ونسخة Java تعيد إنتاج البحث الدقيق نفسه باستخدام أعداد صحيحة كبيرة حيث يلزم، أما نسخة Python فهي طبقة خفيفة تشغّل الحساب الأصلي وتستخرج النتيجة الرقمية النهائية.
لنرمز بـ \(E(D)\) إلى عدد متجهات الأضلاع الأولية التي لا يتجاوز نقصها \(D\). بناء جدول حدود القرص يكلف \(O(r)\) زمنًا و\(O(r)\) ذاكرة. أما توليد الأضلاع المرشحة الحالية وترتيبها فيكلف \(O(E(D)\log E(D))\).
بالنسبة إلى ضلع واحد، يقوم الحل بمسح جميع الإزاحات التي تُبقي طرفي الضلع داخل القرص، وقد يصل ذلك في أسوأ الحالات إلى \(O(r^2)\). وكل إزاحة صالحة تنتج خطين على الأكثر من خطوط المحدد، وكل خط يعطي فترة واحدة متصلة من القيم الصحيحة للرأس الثالث. لذلك فإن حدًا علويًا متساهلًا لجولة بحث واحدة هو \(O(r^2E(D))\). عمليًا يكون الزمن أقل بكثير لأن نافذة النقص تبقى صغيرة، وحد المحيط يحذف كثيرًا من الأضلاع مبكرًا، كما أن فترة \(t\) غالبًا ما تكون قصيرة.
إجمالًا، يعتمد زمن التنفيذ بشدة على البيانات، لكن استهلاك الذاكرة يبقى معتدلًا عند \(O(r+E(D))\)، مع إضافة حالة محلية صغيرة لكل خيط في نسخة C++ المتوازية.