Take a convex quadrilateral \(ABCD\) and let its diagonals meet at \(X\). The diagonals split the four corner angles into eight smaller angles. Problem 177 asks for the number of such quadrilaterals for which all eight of those angles are integers measured in degrees, with shapes identified up to rotation and reflection.
The brute-force version of that question is very redundant. An arbitrary 8-tuple of positive integers does not automatically correspond to a real quadrilateral, and even when it does, the same geometric figure appears many times under different starting vertices or reversed orientations. The implementations solve the problem by finding the right five-parameter description, deriving one trigonometric closure condition, and then canonicalizing the surviving angle data under the dihedral symmetries of the quadrilateral.
The useful viewpoint is to work with the diagonals and the four small triangles that they create. Once the angle data is organized correctly, the geometry separates into a linear part and a multiplicative sine-law part.
Write the eight split angles in cyclic order as four vertex pairs:
$$\bigl(a,p\bigr),\ \bigl(q,r\bigr),\ \bigl(s,c\bigr),\ \bigl(U-c,V-a\bigr).$$
Here the pair \((a,p)\) is the split of angle \(A\), \((q,r)\) is the split of angle \(B\), \((s,c)\) is the split of angle \(C\), and \((U-c,V-a)\) is the split of angle \(D\). The implementations set
$$U=p+q,\qquad V=180-U,\qquad s=V-r.$$
That choice is not arbitrary. In triangle \(ABX\), the angle at the intersection point is \(180-p-q=180-U\). In the opposite triangle \(CDX\), the angle at the intersection point is
$$180-c-(U-c)=180-U,$$
so those vertical angles already match. Likewise, in triangles \(BCX\) and \(DAX\) the intersection angles are both
$$180-r-s=180-V=U.$$
Thus, once \(p\), \(q\), and \(r\) are chosen, the relations \(U=p+q\), \(V=180-U\), and \(s=V-r\) enforce all linear angle constraints coming from the crossing diagonals and the fact that the four interior angles of a convex quadrilateral sum to \(360^\circ\). The remaining free angles are \(a\) and \(c\), with
$$1\le a\le V-1,\qquad 1\le c\le U-1.$$
Now look at the four small triangles adjacent to the sides \(AB\), \(BC\), \(CD\), and \(DA\). The law of sines gives
$$\frac{AX}{BX}=\frac{\sin q}{\sin p},\qquad \frac{BX}{CX}=\frac{\sin s}{\sin r},\qquad \frac{CX}{DX}=\frac{\sin(U-c)}{\sin c},\qquad \frac{DX}{AX}=\frac{\sin a}{\sin(V-a)}.$$
Multiplying the four equations makes the segment lengths telescope, so a necessary condition for the triangles to close up around \(X\) is
$$\frac{\sin q}{\sin p}\cdot\frac{\sin s}{\sin r}\cdot\frac{\sin(U-c)}{\sin c}\cdot\frac{\sin a}{\sin(V-a)}=1.$$
Rearranging gives the invariant used by every implementation:
$$\boxed{\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a).}$$
Within this parameterization the condition is also sufficient. Once one segment such as \(AX\) is chosen, the four sine-law ratios determine \(BX\), \(CX\), and \(DX\). The product condition guarantees that the last ratio returns to the starting length, so the four triangles glue consistently into one convex quadrilateral with the prescribed integer angle data.
The previous identity can be written as
$$\frac{\sin p\,\sin r}{\sin q\,\sin s}=\frac{\sin(U-c)\,\sin a}{\sin c\,\sin(V-a)}.$$
For fixed \(U\), the left-hand side depends only on \((p,q,r)\), because \(s=V-r\) is then determined. The right-hand side depends only on \((a,c)\). That is the entire algorithmic idea.
Define
$$K(p,q,r)=\frac{\sin p\,\sin r}{\sin q\,\sin s},\qquad R_U(a,c)=\frac{\sin(U-c)}{\sin c}\Big/\frac{\sin(V-a)}{\sin a}.$$
Then a valid integer-angled quadrilateral is exactly a match
$$K(p,q,r)=R_U(a,c)$$
with all angles positive. For each fixed \(U\), there are \((U-1)(V-1)\) possible pairs \((a,c)\). The implementations precompute all such \(R_U(a,c)\) values, sort them, and then use binary search to find the pairs that can match a given target \(K(p,q,r)\).
A concrete nontrivial example is
$$p=30,\quad q=60,\quad r=30,\quad a=30,\quad c=60.$$
Then
$$U=p+q=90,\qquad V=90,\qquad s=V-r=60,\qquad U-c=30,\qquad V-a=60.$$
The target value is
$$K=\frac{\sin30\sin30}{\sin60\sin60}=\frac{1/2\cdot1/2}{(\sqrt3/2)(\sqrt3/2)}=\frac13.$$
For the same \(U=90\), the table value at \((a,c)=(30,60)\) is
$$R_{90}(30,60)=\frac{\sin30}{\sin60}\Big/\frac{\sin60}{\sin30}=\frac13,$$
so the trigonometric condition is satisfied. The corresponding vertex pairs are
$$\bigl(30,30\bigr),\ \bigl(60,30\bigr),\ \bigl(60,60\bigr),\ \bigl(30,60\bigr),$$
which give interior angles \(60^\circ,90^\circ,120^\circ,90^\circ\). This is exactly the kind of integer configuration the code stores and deduplicates.
The problem counts shapes, not descriptions. The same quadrilateral can be listed starting from any of its four vertices, and it can also be traversed in the opposite orientation. Therefore the four vertex pairs above have 8 equivalent presentations: 4 cyclic rotations and 4 reflected rotations.
The implementations encode each candidate as the cyclic sequence
$$\bigl(a,p,q,r,s,c,U-c,V-a\bigr)$$
and choose the lexicographically smallest representative among those 8 symmetry images. Counting those canonical representatives is exactly what prevents duplicate quadrilaterals from being included more than once.
The C++, Python, and Java implementations all follow the same three-phase structure.
First the implementation stores \(\sin(d^\circ)\) for every integer \(d\) from \(0\) to \(180\). It also precomputes the basic quotients
$$\frac{\sin(n-k)}{\sin k}$$
for all admissible \(n\) and \(k\). For each \(U\in\{2,\dots,178\}\), it then enumerates every legal pair \((a,c)\), forms \(R_U(a,c)\), tags it with the corresponding angles, and sorts the resulting list by ratio value.
The main loop runs over all positive \(p\), \(q\), and \(r\) with \(U=p+q \lt 180\) and \(1\le r\le V-1\). For each triple it computes \(s=V-r\) and the target \(K(p,q,r)\). A binary search in the precomputed list for the same \(U\) locates the short interval of \((a,c)\) pairs whose floating-point ratio is close enough to \(K\).
Those near matches are not accepted blindly. Each one is rechecked against the original product equation
$$\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a)$$
with a stricter tolerance. This second test filters out candidates that are numerically nearby only because of rounding.
Whenever a candidate passes the verification step, the implementation forms the 8-angle description \((a,p,q,r,s,c,U-c,V-a)\), generates the 8 symmetry-equivalent presentations, keeps the lexicographically smallest one, and inserts it into a set. The final set size is the required number of distinct integer angled quadrilaterals.
The angle range is small and fixed, so the search is finite. A useful exact count is
$$\sum_{U=2}^{178}(U-1)(179-U)=939{,}929,$$
which is both the total number of precomputed \((a,c)\) entries across all ratio tables and the total number of primary \((p,q,r)\) states considered in the main enumeration.
If \(M_U=(U-1)(179-U)\) denotes the size of the table for one fixed \(U\), preprocessing costs \(\sum_U O(M_U\log M_U)\) because each bucket is sorted once. The search phase performs one binary search per \((p,q,r)\) state plus a very small local verification scan around the matching value. Memory usage is dominated by the stored ratio tables and the set of canonical representatives. In practice, the method is fast precisely because it turns geometric existence into a sorted table lookup instead of a naive search over all 8-tuples.
Betrachte ein konvexes Viereck \(ABCD\), dessen Diagonalen sich in \(X\) schneiden. Die Diagonalen zerlegen die vier Eckwinkel in insgesamt acht kleinere Winkel. In Problem 177 soll gezählt werden, wie viele solcher Vierecke existieren, bei denen alle acht Teilwinkel ganzzahlige Gradmaße haben, wobei durch Rotation oder Spiegelung äquivalente Figuren nur einmal gezählt werden.
Eine naive Enumeration aller positiven 8-Tupel wäre stark redundant. Die meisten Winkelmuster beschreiben gar kein echtes Viereck, und selbst gültige Konfigurationen erscheinen mehrfach, wenn man an einem anderen Eckpunkt beginnt oder die Umlaufrichtung umkehrt. Die Implementierungen vermeiden das, indem sie zuerst eine passende Fünf-Parameter-Beschreibung finden, dann eine einzige trigonometrische Schließungsbedingung herleiten und schließlich die verbleibenden Lösungen unter den Dieder-Symmetrien kanonisieren.
Der entscheidende Blickpunkt sind die Diagonalen und die vier kleinen Dreiecke, die durch ihren Schnitt entstehen. In dieser Darstellung zerfällt die Geometrie in einen linearen Teil und in eine multiplikative Bedingung aus dem Sinussatz.
Schreibe die acht Teilwinkel in zyklischer Reihenfolge als vier Eckpunktpaare:
$$\bigl(a,p\bigr),\ \bigl(q,r\bigr),\ \bigl(s,c\bigr),\ \bigl(U-c,V-a\bigr).$$
Dabei beschreibt \((a,p)\) die Aufteilung des Winkels bei \(A\), \((q,r)\) die bei \(B\), \((s,c)\) die bei \(C\) und \((U-c,V-a)\) die bei \(D\). Die Implementierungen setzen
$$U=p+q,\qquad V=180-U,\qquad s=V-r.$$
Diese Wahl kodiert genau die linearen Zwangsbedingungen der Geometrie. Im Dreieck \(ABX\) ist der Winkel im Schnittpunkt \(180-p-q=180-U\). Im gegenüberliegenden Dreieck \(CDX\) erhält man
$$180-c-(U-c)=180-U,$$
also stimmen diese Scheitelwinkel bereits überein. Entsprechend sind die Schnittwinkel in \(BCX\) und \(DAX\) beide
$$180-r-s=180-V=U.$$
Sobald also \(p\), \(q\) und \(r\) gewählt sind, erzwingen die Beziehungen \(U=p+q\), \(V=180-U\) und \(s=V-r\) automatisch die linearen Kompatibilitätsbedingungen der sich schneidenden Diagonalen sowie die Winkelsumme \(360^\circ\) im konvexen Viereck. Frei bleiben nur \(a\) und \(c\), mit
$$1\le a\le V-1,\qquad 1\le c\le U-1.$$
Nun betrachtet man die vier kleinen Dreiecke an den Seiten \(AB\), \(BC\), \(CD\) und \(DA\). Der Sinussatz liefert
$$\frac{AX}{BX}=\frac{\sin q}{\sin p},\qquad \frac{BX}{CX}=\frac{\sin s}{\sin r},\qquad \frac{CX}{DX}=\frac{\sin(U-c)}{\sin c},\qquad \frac{DX}{AX}=\frac{\sin a}{\sin(V-a)}.$$
Multipliziert man diese vier Gleichungen, teleskopieren die Streckenverhältnisse weg. Eine notwendige Bedingung dafür, dass sich die vier Dreiecke um \(X\) zu einem Viereck zusammensetzen, ist also
$$\frac{\sin q}{\sin p}\cdot\frac{\sin s}{\sin r}\cdot\frac{\sin(U-c)}{\sin c}\cdot\frac{\sin a}{\sin(V-a)}=1.$$
Nach Umstellen erhält man genau das Invariante, das in allen Implementierungen geprüft wird:
$$\boxed{\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a).}$$
Innerhalb dieser Parametrisierung ist die Bedingung auch hinreichend. Wählt man zum Beispiel \(AX\) beliebig, dann bestimmen die vier Sinus-Verhältnisse nacheinander \(BX\), \(CX\) und \(DX\). Die Produktbedingung garantiert, dass der letzte Quotient wieder genau zur Startlänge zurückführt. Damit lassen sich die vier Dreiecke konsistent zu einem konvexen Viereck mit den vorgegebenen ganzzahligen Winkeln verkleben.
Die vorige Identität lässt sich schreiben als
$$\frac{\sin p\,\sin r}{\sin q\,\sin s}=\frac{\sin(U-c)\,\sin a}{\sin c\,\sin(V-a)}.$$
Für festes \(U\) hängt die linke Seite nur von \((p,q,r)\) ab, weil \(s=V-r\) dann schon feststeht. Die rechte Seite hängt nur von \((a,c)\) ab. Genau diese Trennung macht die Suche effizient.
Definiere
$$K(p,q,r)=\frac{\sin p\,\sin r}{\sin q\,\sin s},\qquad R_U(a,c)=\frac{\sin(U-c)}{\sin c}\Big/\frac{\sin(V-a)}{\sin a}.$$
Ein gültiges Integer-Angled-Quadrilateral ist damit genau eine Übereinstimmung
$$K(p,q,r)=R_U(a,c)$$
mit ausschließlich positiven Winkeln. Für jedes feste \(U\) gibt es \((U-1)(V-1)\) mögliche Paare \((a,c)\). Die Implementierungen berechnen alle Werte \(R_U(a,c)\) vor, sortieren sie und suchen anschließend per Binärsuche nach den Paaren, die zu einem gegebenen Zielwert \(K(p,q,r)\) passen können.
Ein konkretes, nichttriviales Beispiel ist
$$p=30,\quad q=60,\quad r=30,\quad a=30,\quad c=60.$$
Dann gilt
$$U=p+q=90,\qquad V=90,\qquad s=V-r=60,\qquad U-c=30,\qquad V-a=60.$$
Der Zielwert ist
$$K=\frac{\sin30\sin30}{\sin60\sin60}=\frac{1/2\cdot1/2}{(\sqrt3/2)(\sqrt3/2)}=\frac13.$$
Für dasselbe \(U=90\) hat der Tabellenwert bei \((a,c)=(30,60)\) den Wert
$$R_{90}(30,60)=\frac{\sin30}{\sin60}\Big/\frac{\sin60}{\sin30}=\frac13,$$
also ist die trigonometrische Bedingung erfüllt. Die zugehörigen Eckpunktpaare sind
$$\bigl(30,30\bigr),\ \bigl(60,30\bigr),\ \bigl(60,60\bigr),\ \bigl(30,60\bigr),$$
woraus Innenwinkel von \(60^\circ,90^\circ,120^\circ,90^\circ\) folgen. Genau solche ganzzahligen Konfigurationen werden im Programm gespeichert und dedupliziert.
Gezählt werden geometrische Figuren, nicht ihre Beschreibungen. Dasselbe Viereck kann bei jedem der vier Eckpunkte beginnen, und man kann es außerdem in umgekehrter Orientierung umlaufen. Deshalb besitzen die vier Eckpunktpaare insgesamt 8 äquivalente Darstellungen: 4 zyklische Rotationen und 4 gespiegelte Rotationen.
Die Implementierungen kodieren jeden Kandidaten als zyklische Folge
$$\bigl(a,p,q,r,s,c,U-c,V-a\bigr)$$
und wählen unter diesen 8 Symmetriebildern den lexikographisch kleinsten Repräsentanten. Genau diese Kanonisierung verhindert Mehrfachzählungen.
Die C++-, Python- und Java-Implementierungen folgen alle derselben Dreiphasenstruktur.
Zuerst speichert die Implementierung \(\sin(d^\circ)\) für jedes ganzzahlige \(d\) von \(0\) bis \(180\). Zusätzlich werden die Grundquotienten
$$\frac{\sin(n-k)}{\sin k}$$
für alle zulässigen \(n\) und \(k\) vorbereitet. Für jedes \(U\in\{2,\dots,178\}\) werden danach alle legalen Paare \((a,c)\) durchlaufen, der Wert \(R_U(a,c)\) gebildet, mit den zugehörigen Winkeln gespeichert und die gesamte Liste nach dem Quotienten sortiert.
Die Hauptschleife läuft über alle positiven \(p\), \(q\) und \(r\) mit \(U=p+q \lt 180\) und \(1\le r\le V-1\). Für jedes Tripel werden \(s=V-r\) und der Zielwert \(K(p,q,r)\) berechnet. Eine Binärsuche in der vorberechneten Liste zum selben \(U\) liefert das kurze Intervall jener \((a,c)\)-Paare, deren Gleitkommawert nahe genug an \(K\) liegt.
Diese Treffer werden nicht ungeprüft übernommen. Jeder Kandidat wird noch einmal an der ursprünglichen Produktgleichung
$$\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a)$$
mit einer strengeren Toleranz kontrolliert. Dadurch werden numerische Scheintreffer aussortiert, die nur wegen Rundungsfehlern im Suchfenster lagen.
Besteht ein Kandidat auch den Verifikationsschritt, bildet die Implementierung die 8-Winkel-Beschreibung \((a,p,q,r,s,c,U-c,V-a)\), erzeugt die 8 symmetrieäquivalenten Darstellungen, behält die lexikographisch kleinste davon und fügt sie in eine Menge ein. Die Größe dieser Menge ist genau die gesuchte Anzahl verschiedener Integer Angled Quadrilaterals.
Der Winkelbereich ist klein und fest, daher ist die Suche endlich. Eine nützliche exakte Zahl ist
$$\sum_{U=2}^{178}(U-1)(179-U)=939{,}929,$$
also sowohl die Gesamtzahl aller vorberechneten \((a,c)\)-Einträge über sämtliche Tabellen als auch die Gesamtzahl der primären \((p,q,r)\)-Zustände der Hauptsuche.
Bezeichnet \(M_U=(U-1)(179-U)\) die Größe der Tabelle zu festem \(U\), dann kostet die Vorverarbeitung \(\sum_U O(M_U\log M_U)\), weil jeder Bucket genau einmal sortiert wird. In der Suchphase fällt pro \((p,q,r)\)-Zustand eine Binärsuche plus ein sehr kleiner lokaler Verifikationsscan um den Trefferbereich an. Der Speicherbedarf wird von den gespeicherten Quotiententabellen und der Menge der kanonischen Repräsentanten dominiert. Praktisch ist der Ansatz schnell, weil er geometrische Existenz auf sortierte Nachschlagetabellen reduziert, statt blind über alle 8-Tupel zu iterieren.
Konveks bir \(ABCD\) dörtgeni alıp köşegenlerinin \(X\) noktasında kesiştiğini düşünelim. Köşegenler, dört köşe açısını toplam sekiz küçük açıya ayırır. Problem 177, bu sekiz açının tamamı derece cinsinden tam sayı olan kaç farklı dörtgen bulunduğunu sorar; dönme ve yansıma ile aynı olan şekiller tek bir örnek olarak sayılır.
Bu sorunun kaba kuvvet hâli çok fazla tekrar üretir. Rastgele seçilmiş pozitif bir 8-li açı dizisi çoğu zaman gerçek bir dörtgene karşılık gelmez; karşılık geldiğinde bile aynı geometrik şekil farklı başlangıç köşeleri veya ters dolaşım yönleri altında defalarca ortaya çıkar. Uygulamalar bunu çözmek için önce doğru beş parametreli modeli kurar, sonra tek bir trigonometrik kapanış koşulu çıkarır ve son olarak geçerli açı verilerini dörtgenin dihedral simetrileri altında kanonikleştirir.
En verimli bakış açısı, köşegenler ve onların oluşturduğu dört küçük üçgen üzerinden çalışmaktır. Açı verisi doğru biçimde düzenlenince geometri doğal olarak doğrusal bir parçaya ve sinüs teoreminden gelen çarpımsal bir parçaya ayrılır.
Sekiz bölünmüş açıyı çevresel sırayla dört köşe çifti olarak yazalım:
$$\bigl(a,p\bigr),\ \bigl(q,r\bigr),\ \bigl(s,c\bigr),\ \bigl(U-c,V-a\bigr).$$
Burada \((a,p)\) köşe \(A\)'nın, \((q,r)\) köşe \(B\)'nin, \((s,c)\) köşe \(C\)'nin ve \((U-c,V-a)\) köşe \(D\)'nin köşegen tarafından bölünmüş açı çiftidir. Uygulamalar
$$U=p+q,\qquad V=180-U,\qquad s=V-r$$
tanımlarını kullanır. Bu seçim tesadüfi değildir. \(ABX\) üçgeninde kesişim noktasındaki açı \(180-p-q=180-U\) olur. Karşıdaki \(CDX\) üçgeninde aynı açı
$$180-c-(U-c)=180-U$$
olduğu için karşılıklı açılar zaten eşleşir. Benzer şekilde \(BCX\) ve \(DAX\) üçgenlerindeki kesişim açıları da
$$180-r-s=180-V=U$$
olur. Yani \(p\), \(q\) ve \(r\) seçildiğinde, \(U=p+q\), \(V=180-U\) ve \(s=V-r\) ilişkileri hem kesişen köşegenlerden gelen doğrusal açı kısıtlarını hem de konveks dörtgende iç açıların toplamının \(360^\circ\) olmasını otomatik olarak sağlar. Serbest kalan değişkenler yalnızca \(a\) ve \(c\)'dir:
$$1\le a\le V-1,\qquad 1\le c\le U-1.$$
Şimdi \(AB\), \(BC\), \(CD\) ve \(DA\) kenarlarına komşu dört küçük üçgene bakalım. Sinüs teoremi bize
$$\frac{AX}{BX}=\frac{\sin q}{\sin p},\qquad \frac{BX}{CX}=\frac{\sin s}{\sin r},\qquad \frac{CX}{DX}=\frac{\sin(U-c)}{\sin c},\qquad \frac{DX}{AX}=\frac{\sin a}{\sin(V-a)}$$
eşitliklerini verir. Bu dört oran çarpılınca uzunluklar teleskopik olarak sadeleşir. Dolayısıyla üçgenlerin \(X\) etrafında kapanabilmesi için gerekli koşul
$$\frac{\sin q}{\sin p}\cdot\frac{\sin s}{\sin r}\cdot\frac{\sin(U-c)}{\sin c}\cdot\frac{\sin a}{\sin(V-a)}=1$$
olur. Düzenlersek, bütün uygulamaların kullandığı değişmez elde edilir:
$$\boxed{\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a).}$$
Bu parametreleme içinde bu koşul aynı zamanda yeterlidir. Örneğin \(AX\) uzunluğunu keyfî seçtiğinizde, dört sinüs oranı sırasıyla \(BX\), \(CX\) ve \(DX\)'i belirler. Çarpım koşulu, son oranın tekrar başlangıç uzunluğuna dönmesini garanti eder. Böylece dört küçük üçgen, verilen tam sayılı açı verisiyle tek bir konveks dörtgen oluşturacak biçimde tutarlı olarak birleşir.
Önceki eşitlik şu biçime getirilebilir:
$$\frac{\sin p\,\sin r}{\sin q\,\sin s}=\frac{\sin(U-c)\,\sin a}{\sin c\,\sin(V-a)}.$$
Sabit bir \(U\) için sol taraf yalnızca \((p,q,r)\)'ye bağlıdır; çünkü \(s=V-r\) artık belirlenmiştir. Sağ taraf ise yalnızca \((a,c)\)'ye bağlıdır. Algoritmanın bütün gücü bu ayrımdan gelir.
Şöyle tanımlayalım:
$$K(p,q,r)=\frac{\sin p\,\sin r}{\sin q\,\sin s},\qquad R_U(a,c)=\frac{\sin(U-c)}{\sin c}\Big/\frac{\sin(V-a)}{\sin a}.$$
O hâlde geçerli bir integer angled quadrilateral tam olarak
$$K(p,q,r)=R_U(a,c)$$
eşleşmesidir. Her sabit \(U\) için \((U-1)(V-1)\) adet olası \((a,c)\) çifti vardır. Uygulamalar bütün \(R_U(a,c)\) değerlerini önceden hesaplayıp sıralar; ardından verilen bir \(K(p,q,r)\) hedefi için uygun adayları ikili aramayla bulur.
Somut ve trivial olmayan bir örnek olarak
$$p=30,\quad q=60,\quad r=30,\quad a=30,\quad c=60$$
seçelim. Bu durumda
$$U=p+q=90,\qquad V=90,\qquad s=V-r=60,\qquad U-c=30,\qquad V-a=60.$$
Hedef değer
$$K=\frac{\sin30\sin30}{\sin60\sin60}=\frac{1/2\cdot1/2}{(\sqrt3/2)(\sqrt3/2)}=\frac13$$
olur. Aynı \(U=90\) için tablodaki \((a,c)=(30,60)\) girdisi
$$R_{90}(30,60)=\frac{\sin30}{\sin60}\Big/\frac{\sin60}{\sin30}=\frac13$$
verdiğinden trigonometrik koşul sağlanır. Karşılık gelen köşe çiftleri
$$\bigl(30,30\bigr),\ \bigl(60,30\bigr),\ \bigl(60,60\bigr),\ \bigl(30,60\bigr)$$
olur ve bunların iç açıları \(60^\circ,90^\circ,120^\circ,90^\circ\) çıkar. Kodun saklayıp tekilleştirdiği yapı tam olarak budur.
Problem açıklamaları değil, geometrik şekilleri sayar. Aynı dörtgen dört farklı köşeden başlanarak yazılabilir; ayrıca ters yönde dolaşmak da aynı şekli verir. Bu yüzden yukarıdaki dört köşe çifti toplam 8 eşdeğer sunuma sahiptir: 4 çevresel döndürme ve 4 yansıtılmış döndürme.
Uygulamalar her adayı
$$\bigl(a,p,q,r,s,c,U-c,V-a\bigr)$$
dizisiyle kodlar ve bu 8 simetri görüntüsü arasından leksikografik olarak en küçüğünü seçer. Aynı dörtgenin birden fazla kez sayılmamasını sağlayan şey tam olarak bu kanonik temsil seçimidir.
C++, Python ve Java uygulamaları aynı üç aşamalı yapıyı izler.
Önce \(0\) ile \(180\) arasındaki her tam sayı derece için \(\sin(d^\circ)\) değerleri hesaplanır. Ardından şu temel oranlar hazırlanır:
$$\frac{\sin(n-k)}{\sin k}$$
her uygun \(n\) ve \(k\) için. Daha sonra her \(U\in\{2,\dots,178\}\) değeri için bütün yasal \((a,c)\) çiftleri üretilir, \(R_U(a,c)\) hesaplanır, ilgili açı verisiyle birlikte saklanır ve bu liste oran değerine göre sıralanır.
Ana döngü, \(U=p+q \lt 180\) ve \(1\le r\le V-1\) koşullarını sağlayan bütün pozitif \(p\), \(q\) ve \(r\) değerleri üzerinde çalışır. Her üçlü için \(s=V-r\) ve hedef \(K(p,q,r)\) hesaplanır. Aynı \(U\) için hazırlanmış sıralı tabloda yapılan ikili arama, kayan nokta oranı \(K\)'ye yeterince yakın olan \((a,c)\) aralığını bulur.
Bu yakın eşleşmeler doğrudan kabul edilmez. Her aday, özgün çarpım denklemi
$$\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a)$$
üzerinden daha sıkı bir toleransla tekrar sınanır. Böylece yalnızca yuvarlama nedeniyle yakın görünen yanlış adaylar elenir.
Bir aday doğrulamayı geçtiğinde uygulama 8 açılı tanımı \((a,p,q,r,s,c,U-c,V-a)\) oluşturur, 8 simetri eşdeğerini üretir, bunların leksikografik olarak en küçüğünü seçer ve bir kümeye ekler. Kümenin son boyutu, farklı integer angled quadrilateral sayısının kendisidir.
Açı aralığı küçük ve sabittir; dolayısıyla arama sonludur. Yararlı bir tam sayım şudur:
$$\sum_{U=2}^{178}(U-1)(179-U)=939{,}929,$$
bu hem bütün oran tablolarındaki toplam \((a,c)\) giriş sayısıdır hem de ana taramadaki temel \((p,q,r)\) durumlarının toplamıdır.
Eğer \(M_U=(U-1)(179-U)\), sabit bir \(U\) için tablo boyutu olsun, ön işlem maliyeti her kova bir kez sıralandığı için \(\sum_U O(M_U\log M_U)\) olur. Arama aşamasında her \((p,q,r)\) durumu için bir ikili arama ve eşleşen değerin çevresinde çok küçük bir yerel doğrulama taraması yapılır. Bellek maliyetini esas olarak oran tabloları ile kanonik temsil kümesi belirler. Pratikte yöntem hızlıdır; çünkü geometrik varlık sorununu bütün 8-li diziler üzerinde kör bir arama yerine sıralı bir tablo sorgusuna dönüştürür.
Tomemos un cuadrilátero convexo \(ABCD\) y hagamos que sus diagonales se corten en \(X\). Esas diagonales dividen los cuatro ángulos del contorno en ocho ángulos menores. El Problema 177 pide contar cuántos cuadriláteros de este tipo tienen esos ocho ángulos enteros en grados, considerando iguales las figuras que solo difieren por rotación o reflexión.
La versión ingenua del conteo está llena de redundancias. Un 8-tuplo cualquiera de enteros positivos casi nunca corresponde a un cuadrilátero real, y aun cuando sí lo hace, la misma figura geométrica aparece repetida si se cambia el vértice inicial o si se recorre en sentido contrario. Las implementaciones evitan ese problema encontrando primero una parametrización correcta con cinco grados de libertad, derivando después una única ecuación trigonométrica de cierre y, por último, llevando cada solución a una forma canónica bajo las simetrías diédricas del cuadrilátero.
La forma útil de pensar el problema es a través de las diagonales y de los cuatro triángulos pequeños que ellas generan. Organizados así, los datos angulares se separan en una parte lineal y una condición multiplicativa proveniente de la ley de los senos.
Escribimos los ocho ángulos partidos en orden cíclico como cuatro pares de vértice:
$$\bigl(a,p\bigr),\ \bigl(q,r\bigr),\ \bigl(s,c\bigr),\ \bigl(U-c,V-a\bigr).$$
Aquí \((a,p)\) describe la partición del ángulo en \(A\), \((q,r)\) la de \(B\), \((s,c)\) la de \(C\) y \((U-c,V-a)\) la de \(D\). Las implementaciones fijan
$$U=p+q,\qquad V=180-U,\qquad s=V-r.$$
La razón es geométrica. En el triángulo \(ABX\), el ángulo en el punto de intersección vale \(180-p-q=180-U\). En el triángulo opuesto \(CDX\), ese mismo ángulo es
$$180-c-(U-c)=180-U,$$
de modo que los ángulos verticales ya coinciden. Del mismo modo, en \(BCX\) y \(DAX\) el ángulo de intersección es
$$180-r-s=180-V=U.$$
Por tanto, una vez elegidos \(p\), \(q\) y \(r\), las relaciones \(U=p+q\), \(V=180-U\) y \(s=V-r\) incorporan automáticamente todas las restricciones lineales impuestas por las diagonales que se cruzan y por la suma \(360^\circ\) de los ángulos interiores del cuadrilátero convexo. Los únicos parámetros libres que quedan son \(a\) y \(c\), con
$$1\le a\le V-1,\qquad 1\le c\le U-1.$$
Ahora miramos los cuatro triángulos pequeños adyacentes a los lados \(AB\), \(BC\), \(CD\) y \(DA\). La ley de los senos da
$$\frac{AX}{BX}=\frac{\sin q}{\sin p},\qquad \frac{BX}{CX}=\frac{\sin s}{\sin r},\qquad \frac{CX}{DX}=\frac{\sin(U-c)}{\sin c},\qquad \frac{DX}{AX}=\frac{\sin a}{\sin(V-a)}.$$
Si multiplicamos las cuatro identidades, las longitudes se cancelan telescópicamente. Así, una condición necesaria para que los triángulos cierren alrededor de \(X\) es
$$\frac{\sin q}{\sin p}\cdot\frac{\sin s}{\sin r}\cdot\frac{\sin(U-c)}{\sin c}\cdot\frac{\sin a}{\sin(V-a)}=1.$$
Al reordenar aparece el invariante central de las implementaciones:
$$\boxed{\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a).}$$
Dentro de esta parametrización la condición también es suficiente. Si se fija, por ejemplo, la longitud \(AX\), las cuatro razones del seno determinan sucesivamente \(BX\), \(CX\) y \(DX\). Que el producto sea 1 garantiza que el último cociente regresa exactamente a la longitud inicial, y por eso los cuatro triángulos se pegan de forma consistente en un único cuadrilátero convexo con esos ocho ángulos enteros.
La identidad anterior puede reescribirse como
$$\frac{\sin p\,\sin r}{\sin q\,\sin s}=\frac{\sin(U-c)\,\sin a}{\sin c\,\sin(V-a)}.$$
Para un \(U\) fijo, el lado izquierdo depende solo de \((p,q,r)\), porque \(s=V-r\) ya queda determinado. El lado derecho depende solo de \((a,c)\). Esa separación es exactamente lo que hace eficiente al algoritmo.
Definimos
$$K(p,q,r)=\frac{\sin p\,\sin r}{\sin q\,\sin s},\qquad R_U(a,c)=\frac{\sin(U-c)}{\sin c}\Big/\frac{\sin(V-a)}{\sin a}.$$
Entonces un cuadrilátero entero válido es precisamente una coincidencia
$$K(p,q,r)=R_U(a,c)$$
con todos los ángulos positivos. Para cada \(U\) fijo existen \((U-1)(V-1)\) pares posibles \((a,c)\). Las implementaciones precalculan todos los valores \(R_U(a,c)\), los ordenan y luego usan búsqueda binaria para localizar los pares que pueden corresponder a un objetivo dado \(K(p,q,r)\).
Un ejemplo concreto y no trivial es
$$p=30,\quad q=60,\quad r=30,\quad a=30,\quad c=60.$$
Entonces
$$U=p+q=90,\qquad V=90,\qquad s=V-r=60,\qquad U-c=30,\qquad V-a=60.$$
El valor objetivo es
$$K=\frac{\sin30\sin30}{\sin60\sin60}=\frac{1/2\cdot1/2}{(\sqrt3/2)(\sqrt3/2)}=\frac13.$$
Para ese mismo \(U=90\), la entrada de la tabla en \((a,c)=(30,60)\) vale
$$R_{90}(30,60)=\frac{\sin30}{\sin60}\Big/\frac{\sin60}{\sin30}=\frac13,$$
por lo que la condición trigonométrica se cumple. Los pares de vértice correspondientes son
$$\bigl(30,30\bigr),\ \bigl(60,30\bigr),\ \bigl(60,60\bigr),\ \bigl(30,60\bigr),$$
que producen ángulos interiores \(60^\circ,90^\circ,120^\circ,90^\circ\). Ese es exactamente el tipo de configuración entera que el programa almacena y deduplica.
El problema cuenta figuras, no descripciones. El mismo cuadrilátero puede escribirse empezando en cualquiera de sus cuatro vértices y también puede recorrerse con la orientación opuesta. Por eso los cuatro pares de vértice anteriores tienen 8 presentaciones equivalentes: 4 rotaciones cíclicas y 4 rotaciones reflejadas.
Las implementaciones codifican cada candidato como la secuencia cíclica
$$\bigl(a,p,q,r,s,c,U-c,V-a\bigr)$$
y eligen el representante lexicográficamente menor entre esas 8 imágenes de simetría. Esa forma canónica es exactamente lo que evita contar varias veces el mismo cuadrilátero.
Las implementaciones en C++, Python y Java siguen la misma estructura en tres fases.
Primero la implementación guarda \(\sin(d^\circ)\) para cada entero \(d\) entre \(0\) y \(180\). También precalcula los cocientes básicos
$$\frac{\sin(n-k)}{\sin k}$$
para todos los \(n\) y \(k\) admisibles. Después, para cada \(U\in\{2,\dots,178\}\), enumera todos los pares legales \((a,c)\), forma \(R_U(a,c)\), lo etiqueta con los ángulos correspondientes y ordena la lista resultante por el valor del cociente.
El bucle principal recorre todos los \(p\), \(q\) y \(r\) positivos con \(U=p+q \lt 180\) y \(1\le r\le V-1\). Para cada triple calcula \(s=V-r\) y el objetivo \(K(p,q,r)\). Una búsqueda binaria en la lista precalculada para ese mismo \(U\) localiza el pequeño intervalo de pares \((a,c)\) cuyo cociente en coma flotante está lo bastante cerca de \(K\).
Esas coincidencias cercanas no se aceptan sin más. Cada una se vuelve a comprobar contra la ecuación original
$$\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a)$$
con una tolerancia más estricta. Esa segunda comprobación elimina los falsos positivos creados solo por redondeo numérico.
Cuando un candidato supera la verificación, la implementación forma la descripción de 8 ángulos \((a,p,q,r,s,c,U-c,V-a)\), genera sus 8 presentaciones equivalentes por simetría, conserva la menor en orden lexicográfico y la inserta en un conjunto. El tamaño final de ese conjunto es la cantidad buscada de cuadriláteros angulares enteros distintos.
El rango de ángulos es pequeño y fijo, así que la búsqueda es finita. Un conteo exacto útil es
$$\sum_{U=2}^{178}(U-1)(179-U)=939{,}929,$$
que coincide tanto con el número total de entradas \((a,c)\) precalculadas en todas las tablas como con el número total de estados primarios \((p,q,r)\) examinados en el barrido principal.
Si \(M_U=(U-1)(179-U)\) denota el tamaño de la tabla para un \(U\) fijo, el preproceso cuesta \(\sum_U O(M_U\log M_U)\) porque cada bloque se ordena una sola vez. La fase de búsqueda realiza una búsqueda binaria por cada estado \((p,q,r)\), seguida de una exploración local muy pequeña alrededor del valor coincidente. La memoria está dominada por las tablas de razones almacenadas y por el conjunto de representantes canónicos. En la práctica el método es rápido porque convierte la existencia geométrica en una consulta sobre tablas ordenadas, en lugar de probar a ciegas todos los 8-tuplos.
设 \(ABCD\) 是一个凸四边形，两条对角线交于 \(X\)。对角线会把四个顶点角进一步分成 8 个小角。Problem 177 要求统计这样一些四边形：这 8 个小角全部都是整数度数，并且把旋转或镜像得到的同一图形视为同一个解。
如果直接对 8 个正整数角做暴力枚举，冗余会非常大。大多数 8 元组根本不能拼成真实的凸四边形；即使可以，同一个图形也会因为起点顶点不同或遍历方向相反而重复出现很多次。三个实现真正做的是：先找到一个恰好的五参数描述，再推出一个唯一需要检查的三角恒等式，最后在四边形边界的二面体对称下把等价表示压成同一个规范代表。
最自然的视角不是直接看整个四边形，而是看两条对角线以及它们切出来的四个小三角形。这样整理之后，问题会分成两部分：一部分是线性的角度约束，另一部分是由正弦定理给出的乘法型闭合条件。
把 8 个被对角线分开的角，按沿四边形一周的顺序写成 4 个顶点对：
$$\bigl(a,p\bigr),\ \bigl(q,r\bigr),\ \bigl(s,c\bigr),\ \bigl(U-c,V-a\bigr).$$
这里 \((a,p)\) 是顶点 \(A\) 的两部分，\((q,r)\) 是顶点 \(B\) 的两部分，\((s,c)\) 是顶点 \(C\) 的两部分，\((U-c,V-a)\) 是顶点 \(D\) 的两部分。实现中固定
$$U=p+q,\qquad V=180-U,\qquad s=V-r.$$
这一组选取正好把几何中的线性条件编码进去。因为在三角形 \(ABX\) 中，交点处的角为 \(180-p-q=180-U\)；而在对面的三角形 \(CDX\) 中，该角为
$$180-c-(U-c)=180-U,$$
所以这一对对顶角自动相等。同理，在 \(BCX\) 与 \(DAX\) 中，交点处的角都等于
$$180-r-s=180-V=U.$$
因此，一旦选定 \(p\)、\(q\) 与 \(r\)，关系 \(U=p+q\)、\(V=180-U\)、\(s=V-r\) 就已经自动满足了“对角线相交时对顶角相等”以及“凸四边形内角和为 \(360^\circ\)”这些线性约束。剩下真正自由的只有 \(a\) 和 \(c\)，并且必须满足
$$1\le a\le V-1,\qquad 1\le c\le U-1.$$
接下来考察靠近四条边 \(AB\)、\(BC\)、\(CD\)、\(DA\) 的四个小三角形。正弦定理给出
$$\frac{AX}{BX}=\frac{\sin q}{\sin p},\qquad \frac{BX}{CX}=\frac{\sin s}{\sin r},\qquad \frac{CX}{DX}=\frac{\sin(U-c)}{\sin c},\qquad \frac{DX}{AX}=\frac{\sin a}{\sin(V-a)}.$$
把这四个式子相乘，长度比会望远镜式消去，因此四个小三角形能围绕 \(X\) 正确闭合的必要条件是
$$\frac{\sin q}{\sin p}\cdot\frac{\sin s}{\sin r}\cdot\frac{\sin(U-c)}{\sin c}\cdot\frac{\sin a}{\sin(V-a)}=1.$$
整理后得到实现真正检查的核心不变量：
$$\boxed{\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a).}$$
在这套参数化中，它不仅是必要条件，也是充分条件。因为如果先任选一条长度，例如 \(AX\)，那么这四个正弦比会依次唯一确定 \(BX\)、\(CX\)、\(DX\)。乘积恰好为 1，意味着最后一个比例又回到了起始长度，于是四个小三角形可以无矛盾地拼成一个凸四边形，并且它的 8 个分裂角正好就是这些整数值。
上面的恒等式可以改写成
$$\frac{\sin p\,\sin r}{\sin q\,\sin s}=\frac{\sin(U-c)\,\sin a}{\sin c\,\sin(V-a)}.$$
对于固定的 \(U\)，左边只依赖于 \((p,q,r)\)，因为此时 \(s=V-r\) 已经确定；右边只依赖于 \((a,c)\)。算法的全部效率都来自这一步分离。
记
$$K(p,q,r)=\frac{\sin p\,\sin r}{\sin q\,\sin s},\qquad R_U(a,c)=\frac{\sin(U-c)}{\sin c}\Big/\frac{\sin(V-a)}{\sin a}.$$
于是一个合法的整数角四边形，等价于找到满足
$$K(p,q,r)=R_U(a,c)$$
的正角数据。对每个固定的 \(U\)，共有 \((U-1)(V-1)\) 个可能的 \((a,c)\) 组合。实现先把这些 \(R_U(a,c)\) 全部算出来并排序，然后对每个目标值 \(K(p,q,r)\) 做二分查找，快速定位可能匹配的 \((a,c)\) 区间。
一个具体而且并不平凡的例子是
$$p=30,\quad q=60,\quad r=30,\quad a=30,\quad c=60.$$
这时
$$U=p+q=90,\qquad V=90,\qquad s=V-r=60,\qquad U-c=30,\qquad V-a=60.$$
对应的目标值为
$$K=\frac{\sin30\sin30}{\sin60\sin60}=\frac{1/2\cdot1/2}{(\sqrt3/2)(\sqrt3/2)}=\frac13.$$
而在同一个 \(U=90\) 的表中，\((a,c)=(30,60)\) 的值为
$$R_{90}(30,60)=\frac{\sin30}{\sin60}\Big/\frac{\sin60}{\sin30}=\frac13,$$
所以三角条件确实成立。对应的四个顶点对是
$$\bigl(30,30\bigr),\ \bigl(60,30\bigr),\ \bigl(60,60\bigr),\ \bigl(30,60\bigr),$$
因此四个内角分别是 \(60^\circ,90^\circ,120^\circ,90^\circ\)。程序收集并去重的，正是这种整数角配置。
题目要求统计的是几何图形，而不是书写方式。同一个四边形可以从任意一个顶点开始记录，也可以按相反方向绕一圈。因此上面的四个顶点对一共对应 8 种等价表示：4 种循环旋转，以及 4 种镜像后的旋转。
实现把每个候选解编码成
$$\bigl(a,p,q,r,s,c,U-c,V-a\bigr)$$
这条循环序列，然后在全部 8 个对称像里选取字典序最小的那个作为规范代表。最后只统计这些规范代表，就不会把同一个四边形重复记数。
C++、Python 和 Java 三个实现都遵循同样的三阶段结构。
首先，程序会把所有整数角 \(d=0,1,\dots,180\) 的 \(\sin(d^\circ)\) 预先算好。同时还会预计算基本商
$$\frac{\sin(n-k)}{\sin k}$$
对所有允许的 \(n\) 与 \(k\)。随后，对每个 \(U\in\{2,\dots,178\}\)，枚举所有合法的 \((a,c)\)，计算 \(R_U(a,c)\)，把它和对应角数据一起存入数组，再按比值大小排序。
主循环遍历所有满足 \(U=p+q \lt 180\) 且 \(1\le r\le V-1\) 的正整数 \(p,q,r\)。对每个三元组，程序算出 \(s=V-r\) 和目标值 \(K(p,q,r)\)。然后在相同 \(U\) 的预排序表中做二分查找，找出那些浮点比值足够接近 \(K\) 的 \((a,c)\) 候选区间。
这些“接近”并不会直接被接受。每个候选都会再用原始乘积方程
$$\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a)$$
做一次更严格的数值检查。这样可以把只因为浮点误差而落进搜索窗口的伪匹配剔除掉。
一旦候选通过验证，程序就构造 8 角描述 \((a,p,q,r,s,c,U-c,V-a)\)，生成它在 8 个对称操作下的等价表示，保留字典序最小的那个，并插入集合。集合最终的大小就是所求的不同整数角四边形数量。
角度范围很小而且固定，因此整个搜索是有限的。一个很有用的精确计数是
$$\sum_{U=2}^{178}(U-1)(179-U)=939{,}929,$$
它既是所有 \(U\) 上预计算的 \((a,c)\) 表项总数，也是主循环中基础 \((p,q,r)\) 状态的总数。
如果记 \(M_U=(U-1)(179-U)\) 为某个固定 \(U\) 的表大小，那么预处理代价是 \(\sum_U O(M_U\log M_U)\)，因为每个桶只排序一次。搜索阶段对每个 \((p,q,r)\) 状态进行一次二分查找，并在命中值附近做很小范围的复核扫描。内存主要消耗在比值表和规范代表集合上。这个方法之所以足够快，是因为它把“几何上是否存在”转化成了有序表查找，而不是对所有 8 元组做盲目穷举。
Рассмотрим выпуклый четырехугольник \(ABCD\), диагонали которого пересекаются в точке \(X\). Диагонали разбивают четыре угла при вершинах на восемь меньших углов. В задаче 177 нужно посчитать количество таких четырехугольников, у которых все эти восемь углов выражаются целым числом градусов, причем фигуры, совпадающие с точностью до поворота или отражения, считаются одинаковыми.
Наивный перебор всех положительных 8-кортежей слишком избыточен. Большинство наборов углов вовсе не соответствует реальному выпуклому четырехугольнику, а те, что соответствуют, многократно повторяются при выборе другой стартовой вершины или противоположного направления обхода. Поэтому реализации сначала строят правильную параметризацию с пятью степенями свободы, затем выводят одно тригонометрическое условие замыкания и после этого канонизируют каждое решение относительно диэдральных симметрий границы четырехугольника.
Ключевая идея состоит в том, чтобы смотреть не на весь четырехугольник сразу, а на диагонали и на четыре маленьких треугольника, которые они образуют. В такой записи геометрия естественно распадается на линейные угловые соотношения и на мультипликативное условие, полученное из теоремы синусов.
Запишем восемь разбиений углов в циклическом порядке как четыре пары при вершинах:
$$\bigl(a,p\bigr),\ \bigl(q,r\bigr),\ \bigl(s,c\bigr),\ \bigl(U-c,V-a\bigr).$$
Здесь \((a,p)\) задает разбиение угла при \(A\), \((q,r)\) при \(B\), \((s,c)\) при \(C\), а \((U-c,V-a)\) при \(D\). Реализации используют соотношения
$$U=p+q,\qquad V=180-U,\qquad s=V-r.$$
Это именно те линейные связи, которые требуются геометрией. В треугольнике \(ABX\) угол при точке пересечения равен \(180-p-q=180-U\). В противоположном треугольнике \(CDX\) тот же угол равен
$$180-c-(U-c)=180-U,$$
поэтому одна пара вертикальных углов совпадает автоматически. Аналогично, в \(BCX\) и \(DAX\) угол при пересечении равен
$$180-r-s=180-V=U.$$
Значит, после выбора \(p\), \(q\) и \(r\) связи \(U=p+q\), \(V=180-U\) и \(s=V-r\) уже учитывают все линейные ограничения, возникающие из пересечения диагоналей и из того факта, что сумма внутренних углов выпуклого четырехугольника равна \(360^\circ\). Свободными остаются только \(a\) и \(c\), причем
$$1\le a\le V-1,\qquad 1\le c\le U-1.$$
Теперь посмотрим на четыре малых треугольника, прилегающих к сторонам \(AB\), \(BC\), \(CD\) и \(DA\). Теорема синусов дает
$$\frac{AX}{BX}=\frac{\sin q}{\sin p},\qquad \frac{BX}{CX}=\frac{\sin s}{\sin r},\qquad \frac{CX}{DX}=\frac{\sin(U-c)}{\sin c},\qquad \frac{DX}{AX}=\frac{\sin a}{\sin(V-a)}.$$
Если перемножить эти четыре отношения, длины телескопически сократятся. Поэтому необходимое условие того, что четыре треугольника действительно замыкаются вокруг \(X\), имеет вид
$$\frac{\sin q}{\sin p}\cdot\frac{\sin s}{\sin r}\cdot\frac{\sin(U-c)}{\sin c}\cdot\frac{\sin a}{\sin(V-a)}=1.$$
После перестановки множителей получаем центральное инвариантное равенство, которое проверяют все реализации:
$$\boxed{\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a).}$$
Внутри этой параметризации условие является и достаточным. Достаточно выбрать, например, длину \(AX\); тогда четыре отношения синусов последовательно определяют \(BX\), \(CX\) и \(DX\). Равенство произведений гарантирует, что последний шаг возвращает нас ровно к исходной длине, а значит, четыре малых треугольника можно согласованно склеить в один выпуклый четырехугольник с заданными целыми углами.
Предыдущее равенство переписывается так:
$$\frac{\sin p\,\sin r}{\sin q\,\sin s}=\frac{\sin(U-c)\,\sin a}{\sin c\,\sin(V-a)}.$$
При фиксированном \(U\) левая часть зависит только от \((p,q,r)\), поскольку \(s=V-r\) уже задан. Правая часть зависит только от \((a,c)\). Именно эта развязка и делает алгоритм эффективным.
Обозначим
$$K(p,q,r)=\frac{\sin p\,\sin r}{\sin q\,\sin s},\qquad R_U(a,c)=\frac{\sin(U-c)}{\sin c}\Big/\frac{\sin(V-a)}{\sin a}.$$
Тогда допустимый integer angled quadrilateral соответствует ровно одному совпадению
$$K(p,q,r)=R_U(a,c)$$
при всех положительных углах. Для каждого фиксированного \(U\) существует \((U-1)(V-1)\) возможных пар \((a,c)\). Реализации заранее вычисляют все значения \(R_U(a,c)\), сортируют их, а затем бинарным поиском находят те пары, которые могут совпасть с данным целевым значением \(K(p,q,r)\).
Возьмем конкретный нетривиальный пример
$$p=30,\quad q=60,\quad r=30,\quad a=30,\quad c=60.$$
Тогда
$$U=p+q=90,\qquad V=90,\qquad s=V-r=60,\qquad U-c=30,\qquad V-a=60.$$
Целевое значение равно
$$K=\frac{\sin30\sin30}{\sin60\sin60}=\frac{1/2\cdot1/2}{(\sqrt3/2)(\sqrt3/2)}=\frac13.$$
Для того же \(U=90\) табличное значение в точке \((a,c)=(30,60)\) равно
$$R_{90}(30,60)=\frac{\sin30}{\sin60}\Big/\frac{\sin60}{\sin30}=\frac13,$$
поэтому тригонометрическое условие выполнено. Соответствующие пары при вершинах имеют вид
$$\bigl(30,30\bigr),\ \bigl(60,30\bigr),\ \bigl(60,60\bigr),\ \bigl(30,60\bigr),$$
а внутренние углы равны \(60^\circ,90^\circ,120^\circ,90^\circ\). Именно такие целочисленные конфигурации программа сохраняет и очищает от дубликатов.
Задача считает геометрические фигуры, а не способы их записи. Один и тот же четырехугольник можно начать перечислять с любой из четырех вершин, и его можно обходить в противоположном направлении. Поэтому четыре пары вершин имеют 8 эквивалентных представлений: 4 циклических поворота и 4 отраженных поворота.
Реализации кодируют каждый кандидат циклической последовательностью
$$\bigl(a,p,q,r,s,c,U-c,V-a\bigr)$$
и выбирают лексикографически минимального представителя среди всех 8 симметричных образов. Именно эта канонизация устраняет повторный счет одного и того же четырехугольника.
Реализации на C++, Python и Java следуют одной и той же трехфазной схеме.
Сначала программа сохраняет \(\sin(d^\circ)\) для каждого целого \(d\) от \(0\) до \(180\). Затем она предварительно вычисляет базовые отношения
$$\frac{\sin(n-k)}{\sin k}$$
для всех допустимых \(n\) и \(k\). После этого для каждого \(U\in\{2,\dots,178\}\) перечисляются все допустимые пары \((a,c)\), вычисляется \(R_U(a,c)\), значение снабжается соответствующими углами, и весь список сортируется по величине отношения.
Главный цикл проходит по всем положительным \(p\), \(q\) и \(r\), удовлетворяющим \(U=p+q \lt 180\) и \(1\le r\le V-1\). Для каждого тройного состояния вычисляются \(s=V-r\) и целевое значение \(K(p,q,r)\). Бинарный поиск в заранее отсортированном списке для того же \(U\) находит короткий интервал пар \((a,c)\), чьи значения в плавающей точке достаточно близки к \(K\).
Эти совпадения не принимаются автоматически. Каждый кандидат повторно проверяется по исходному произведению
$$\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a)$$
с более строгим допуском. Такая повторная проверка отсекает численные ложные срабатывания, появившиеся только из-за округления.
Если кандидат проходит проверку, программа формирует 8-угловое описание \((a,p,q,r,s,c,U-c,V-a)\), порождает все 8 симметрически эквивалентных представлений, оставляет лексикографически минимальное и вставляет его в множество. Конечный размер множества и есть искомое число различных целочисленно-угловых четырехугольников.
Диапазон углов мал и фиксирован, поэтому весь поиск конечен. Полезное точное количество равно
$$\sum_{U=2}^{178}(U-1)(179-U)=939{,}929,$$
и это одновременно общее число предвычисленных записей \((a,c)\) во всех таблицах и общее число базовых состояний \((p,q,r)\), перебираемых в основном проходе.
Если \(M_U=(U-1)(179-U)\) обозначает размер таблицы для фиксированного \(U\), то предобработка стоит \(\sum_U O(M_U\log M_U)\), потому что каждый блок сортируется один раз. В фазе поиска на каждое состояние \((p,q,r)\) приходится один бинарный поиск и очень маленький локальный просмотр около найденного значения. Память в основном расходуется на сами таблицы отношений и на множество канонических представителей. Практическая скорость достигается именно потому, что задача существования сводится к поиску по отсортированной таблице, а не к слепому перебору всех 8-кортежей.
لنأخذ رباعيًا محدبًا \(ABCD\) ولتتقاطع قطراه في النقطة \(X\). هذان القطـران يقسمان زوايا الرؤوس الأربع إلى ثماني زوايا أصغر. مسألة 177 تطلب عدّ عدد الرباعيات من هذا النوع التي تكون فيها الزوايا الثماني كلها أعدادًا صحيحة بالدرجات، مع اعتبار الأشكال المتطابقة بالدوران أو الانعكاس شكلًا واحدًا فقط.
العدّ الساذج لكل الثمانيات الممكنة من الزوايا الموجبة مليء بالتكرار. فمعظم الثمانيات لا تمثل رباعيًا حقيقيًا أصلًا، وحتى عندما تمثله فإن الشكل نفسه يظهر مرات كثيرة إذا بدأنا من رأس مختلف أو سرنا حوله بالاتجاه المعاكس. لذلك تبني التطبيقات أولًا توصيفًا صحيحًا بخمسة معاملات، ثم تستخرج شرط إغلاق مثلثيًا واحدًا، ثم تحوّل كل حل صالح إلى ممثل معياري تحت تماثلات المجموعة الثنائية لحدود الرباعي.
الرؤية المفيدة هنا ليست النظر إلى الرباعي دفعة واحدة، بل إلى القطرين والأربعة مثلثات الصغيرة التي يصنعانها. بعد هذا التنظيم تنقسم الهندسة إلى جزء خطي خاص بالزوايا، وجزء ضربي يأتي من قانون الجيوب.
نكتب الزوايا المنقسمة الثماني على الترتيب الدوري في صورة أربعة أزواج للرؤوس:
$$\bigl(a,p\bigr),\ \bigl(q,r\bigr),\ \bigl(s,c\bigr),\ \bigl(U-c,V-a\bigr).$$
فالزوج \((a,p)\) هو تقسيم زاوية \(A\)، والزوج \((q,r)\) لزاوية \(B\)، والزوج \((s,c)\) لزاوية \(C\)، والزوج \((U-c,V-a)\) لزاوية \(D\). وتستخدم التطبيقات العلاقات
$$U=p+q,\qquad V=180-U,\qquad s=V-r.$$
وهذا ليس اختيارًا اعتباطيًا. ففي المثلث \(ABX\) تكون الزاوية عند نقطة التقاطع مساوية لـ \(180-p-q=180-U\). وفي المثلث المقابل \(CDX\) تكون الزاوية نفسها
$$180-c-(U-c)=180-U,$$
فتتطابق زاويتان متقابلتان بالرأس تلقائيًا. وبالمثل، تكون الزاوية عند التقاطع في المثلثين \(BCX\) و\(DAX\) مساوية دائمًا لـ
$$180-r-s=180-V=U.$$
إذن بمجرد اختيار \(p\) و\(q\) و\(r\)، فإن العلاقات \(U=p+q\) و\(V=180-U\) و\(s=V-r\) تفرض تلقائيًا كل القيود الخطية الناتجة عن تقاطع القطرين وعن حقيقة أن مجموع الزوايا الداخلية للرباعي المحدب هو \(360^\circ\). ولا يبقى حرًا إلا \(a\) و\(c\)، مع الشرطين
$$1\le a\le V-1,\qquad 1\le c\le U-1.$$
ننظر الآن إلى المثلثات الأربع الصغيرة الملاصقة للأضلاع \(AB\) و\(BC\) و\(CD\) و\(DA\). يعطي قانون الجيوب
$$\frac{AX}{BX}=\frac{\sin q}{\sin p},\qquad \frac{BX}{CX}=\frac{\sin s}{\sin r},\qquad \frac{CX}{DX}=\frac{\sin(U-c)}{\sin c},\qquad \frac{DX}{AX}=\frac{\sin a}{\sin(V-a)}.$$
وعند ضرب هذه العلاقات الأربع تتلاشى أطوال المقاطع على نحو تلسكوبي. لذلك يكون الشرط الضروري لكي تنغلق المثلثات الأربع حول \(X\) هو
$$\frac{\sin q}{\sin p}\cdot\frac{\sin s}{\sin r}\cdot\frac{\sin(U-c)}{\sin c}\cdot\frac{\sin a}{\sin(V-a)}=1.$$
وبإعادة الترتيب نحصل على الثابت الأساسي الذي تتحقق منه جميع التطبيقات:
$$\boxed{\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a).}$$
وفي هذا الترميز لا يكون الشرط لازمًا فقط بل كافيًا أيضًا. فإذا اخترنا طولًا واحدًا مثل \(AX\)، فإن نسب الجيوب الأربع تحدد تباعًا \(BX\) و\(CX\) و\(DX\). وكون حاصل الضرب يساوي 1 يضمن أن آخر نسبة تعيدنا تمامًا إلى الطول الابتدائي، ولذلك يمكن لصق المثلثات الأربع بطريقة متسقة لتكوين رباعي محدب يملك هذه الزوايا الصحيحة بالضبط.
يمكن كتابة الهوية السابقة على الصورة
$$\frac{\sin p\,\sin r}{\sin q\,\sin s}=\frac{\sin(U-c)\,\sin a}{\sin c\,\sin(V-a)}.$$
عند تثبيت \(U\)، يعتمد الطرف الأيسر فقط على \((p,q,r)\)، لأن \(s=V-r\) يصبح معلومًا حينها. أما الطرف الأيمن فيعتمد فقط على \((a,c)\). وهذه هي الفكرة الخوارزمية كلها.
نعرّف
$$K(p,q,r)=\frac{\sin p\,\sin r}{\sin q\,\sin s},\qquad R_U(a,c)=\frac{\sin(U-c)}{\sin c}\Big/\frac{\sin(V-a)}{\sin a}.$$
وعندئذ يكون الرباعي ذو الزوايا الصحيحة صالحًا بالضبط عندما نجد تطابقًا
$$K(p,q,r)=R_U(a,c)$$
مع كون جميع الزوايا موجبة. ولكل \(U\) ثابت يوجد \((U-1)(V-1)\) زوجًا ممكنًا من \((a,c)\). تقوم التطبيقات بحساب جميع قيم \(R_U(a,c)\) مسبقًا وترتيبها، ثم تستخدم البحث الثنائي لتحديد الأزواج التي يمكن أن تطابق القيمة الهدف \(K(p,q,r)\).
مثال واضح وغير تافه هو
$$p=30,\quad q=60,\quad r=30,\quad a=30,\quad c=60.$$
وعندئذ
$$U=p+q=90,\qquad V=90,\qquad s=V-r=60,\qquad U-c=30,\qquad V-a=60.$$
وتكون قيمة الهدف
$$K=\frac{\sin30\sin30}{\sin60\sin60}=\frac{1/2\cdot1/2}{(\sqrt3/2)(\sqrt3/2)}=\frac13.$$
ولنفس \(U=90\) نجد أن قيمة الجدول عند \((a,c)=(30,60)\) هي
$$R_{90}(30,60)=\frac{\sin30}{\sin60}\Big/\frac{\sin60}{\sin30}=\frac13,$$
ومن ثم يتحقق الشرط المثلثي. وأزواج الرؤوس الموافقة هي
$$\bigl(30,30\bigr),\ \bigl(60,30\bigr),\ \bigl(60,60\bigr),\ \bigl(30,60\bigr),$$
فتكون الزوايا الداخلية \(60^\circ,90^\circ,120^\circ,90^\circ\). وهذا بالضبط هو نوع التهيئة الصحيحة التي تخزنها الشيفرة وتزيل تكرارها.
المطلوب عدّ الأشكال الهندسية لا طرق وصفها. فالرباعي نفسه يمكن كتابته بدءًا من أي رأس من رؤوسه الأربعة، كما يمكن اجتيازه بالاتجاه المعاكس. لذلك تمتلك أزواج الرؤوس الأربعة السابقة 8 عروض متكافئة: 4 دورانات دورية و4 دورانات بعد انعكاس.
تُمثّل التطبيقات كل مرشح بالمتتالية الدورية
$$\bigl(a,p,q,r,s,c,U-c,V-a\bigr)$$
ثم تختار أصغر ممثل معجميًا بين الصور الثماني الناتجة عن التماثل. وهذا التمثيل المعياري هو ما يمنع عدّ الرباعي نفسه أكثر من مرة.
تتبع تطبيقات C++ وPython وJava البنية نفسها ذات المراحل الثلاث.
أولًا تحسب الشيفرة \(\sin(d^\circ)\) لكل درجة صحيحة \(d\) من \(0\) إلى \(180\). كما تحسب مسبقًا النسب الأساسية
$$\frac{\sin(n-k)}{\sin k}$$
لكل \(n\) و\(k\) المسموحين. ثم لكل \(U\in\{2,\dots,178\}\) تُعدّ كل الأزواج القانونية \((a,c)\)، وتُحسب \(R_U(a,c)\)، وتُخزَّن مع بيانات الزوايا الموافقة، ثم يُرتَّب الجدول بحسب قيمة النسبة.
تجري الحلقة الرئيسية على كل \(p\) و\(q\) و\(r\) الموجبة التي تحقق \(U=p+q \lt 180\) و\(1\le r\le V-1\). ولكل ثلاثي تُحسب \(s=V-r\) والقيمة الهدف \(K(p,q,r)\). بعد ذلك يحدد البحث الثنائي داخل الجدول المرتب لنفس \(U\) المجال الصغير من الأزواج \((a,c)\) التي تقع نسبتها العشرية قريبًا بما يكفي من \(K\).
هذه المطابقات القريبة لا تُقبل مباشرة. فكل مرشح يُعاد فحصه بواسطة معادلة الضرب الأصلية
$$\sin q\,\sin s\,\sin(U-c)\,\sin a=\sin p\,\sin r\,\sin c\,\sin(V-a)$$
مع سماحية أدق. وبهذا تُستبعد المطابقات الوهمية التي ظهرت فقط بسبب أخطاء التقريب العشري.
إذا اجتاز المرشح خطوة التحقق، تُكوّن الشيفرة الوصف ذي الزوايا الثماني \((a,p,q,r,s,c,U-c,V-a)\)، وتولد صوره الثماني المتكافئة بالتماثل، ثم تحتفظ بالأصغر معجميًا وتدرجه في مجموعة. وحجم هذه المجموعة في النهاية هو العدد المطلوب للرباعيات المختلفة ذات الزوايا الصحيحة.
مجال الزوايا صغير وثابت، ولذلك فالبحث كله منتهٍ. ومن المفيد تسجيل العدد الدقيق
$$\sum_{U=2}^{178}(U-1)(179-U)=939{,}929,$$
وهو في الوقت نفسه العدد الكلي لمدخلات \((a,c)\) المحسوبة مسبقًا في جميع الجداول، والعدد الكلي للحالات الأساسية \((p,q,r)\) التي يمر عليها التعداد الرئيسي.
إذا رمزنا إلى حجم جدول \(U\) الثابت بالكمية \(M_U=(U-1)(179-U)\)، فإن كلفة التحضير هي \(\sum_U O(M_U\log M_U)\) لأن كل دلو يُرتَّب مرة واحدة. وفي مرحلة البحث توجد عملية بحث ثنائي واحدة لكل حالة \((p,q,r)\)، يتبعها فحص محلي صغير جدًا قرب القيمة المطابقة. وتهيمن على الذاكرة جداول النسب المخزنة ومجموعة الممثلين المعياريين. والسبب في سرعة هذه الطريقة عمليًا هو أنها تحول شرط الوجود الهندسي إلى استعلام في جدول مرتب بدلًا من تجربة جميع الثمانيات الممكنة عشوائيًا.