The goal is to count lattice polygons whose edge lengths are integers and whose perimeter is at most \(N\). For the Project Euler target we need \(P(120)\). The code does not brute-force polygons directly; instead it builds them from admissible edge directions and uses dynamic programming on displacement and remaining perimeter.
An edge vector \((x,y)\) has integer Euclidean length exactly when
$$x^2+y^2=\ell^2$$
for some integer \(\ell\). To avoid representing the same direction many times, the code keeps only primitive vectors
$$\gcd(x,y)=1,$$
and later allows any positive multiple \(g(x,y)\), whose length is \(g\ell\). Because no edge of a genuine polygon can exceed half the total perimeter, it is enough to generate primitive vectors with
$$\ell \le \left\lfloor \frac{N-1}{2}\right\rfloor.$$
The primitive directions are sorted by angle \(\theta=\operatorname{atan2}(y,x)\). This gives a canonical way to describe a polygon boundary: after choosing a distinguished lowest vertex as the origin, the boundary edges can be read in nondecreasing angular order. Without this step, the same polygon could be generated many times from different cyclic starting points or different presentations of parallel edges.
The state stored by the program is
$$ (X,Y,r), $$
where \((X,Y)\) is the current displacement from the chosen origin and \(r\) is the remaining perimeter budget. If we use the current primitive direction \((dx,dy)\) with primitive length \(\ell\) and multiplicity \(g\ge 1\), then the transition is
$$ (X,Y,r)\longrightarrow (X+g\,dx,\;Y+g\,dy,\;r-g\ell). $$
In other words, the DP is not guessing whole polygons at once; it is appending one angularly ordered edge block at a time.
The transition is accepted only if two geometric filters hold.
Upper-half-plane rule. The code requires
$$Y_{\text{new}}\ge 0.$$
This chooses the lowest vertex of the polygon as the origin and forbids the partial walk from going below it. That gives one canonical representative instead of counting vertical translations or cyclic rotations of the same boundary.
Return-to-origin feasibility. The code also requires
$$X_{\text{new}}^2+Y_{\text{new}}^2\le r_{\text{new}}^2.$$
By the triangle inequality, if the Euclidean distance back to the origin already exceeds the remaining perimeter, closure is impossible. This single test removes a huge number of hopeless states.
After all directions have been processed, every state with displacement \((0,0)\) corresponds to a closed walk built from admissible integer-length edges. So the DP sums all states with origin key over every remaining budget level.
However, this raw count still includes two non-polygonal artifacts:
The empty walk. The initial state at the origin contributes one trivial closure and must be removed.
Two-edge backtracks. For any primitive direction of length \(\ell\), choosing an edge of length \(g\ell\) and then the opposite edge of the same length yields a closed degenerate segment of perimeter \(2g\ell\), not a genuine polygon. The code counts how many such objects exist via
$$\sum_{\text{primitive }v}\left\lfloor\frac{N}{2\ell(v)}\right\rfloor,$$
then divides by \(2\) because each direction and its opposite both appear in the vector list.
That is exactly why the final answer is computed as
$$\text{answer}=\Bigl(\text{all closed states}\Bigr)-1-\text{diagonal}.$$
The implementation validates itself on
$$P(4)=1,\qquad P(30)=3655,\qquad P(60)=891045.$$
For \(N=4\), the only polygon is the unit square, so the first checkpoint is easy to visualize. The program then computes
$$P(120)=3600060866.$$
The function init_vectors generates all primitive integer vectors with integer norm up to \((N-1)/2\), then sorts them by angle. The array arr[r] is a hash map of reachable displacements at remaining budget \(r\). It starts from the origin at budget \(N\). For each direction, the code tries every admissible multiplicity \(g\), applies the two pruning rules, and adds the resulting state into the hash map for the smaller remaining budget. Finally it sums all origin states and subtracts the empty path and the degenerate two-edge corrections.
If \(V\) is the number of primitive directions and \(S_r\) is the number of reachable states at remaining budget \(r\), then the running time is roughly
$$O\!\left(\sum_{v\in V}\sum_r S_r\,M_{v,r}\right),$$
where \(M_{v,r}\) is the number of multiplicities \(g\) that still fit inside budget \(r\). Memory usage is the total size of the hash maps \(\texttt{arr}[0],\dots,\texttt{arr}[N]\). The essential gain comes from the geometric pruning, especially the distance-to-origin bound.
Gesucht ist die Anzahl von Gitterpolygonen mit ganzzahliger Kantenlänge und Umfang höchstens \(N\). Für Project Euler wird \(P(120)\) benötigt. Der Code erzeugt Polygone nicht direkt, sondern baut sie aus zulässigen Richtungen auf und verwendet ein DP über Verschiebungsvektor und Restumfang.
Ein Kantenvektor \((x,y)\) hat genau dann ganzzahlige Länge, wenn
$$x^2+y^2=\ell^2$$
für ein ganzzahliges \(\ell\) gilt. Um dieselbe Richtung nicht mehrfach zu erzeugen, behält der Code nur primitive Vektoren mit
$$\gcd(x,y)=1.$$
Später sind beliebige positive Vielfache \(g(x,y)\) erlaubt; deren Länge ist \(g\ell\). Da in einem echten Polygon keine Kante länger als die halbe Gesamtlänge sein kann, genügt
$$\ell \le \left\lfloor \frac{N-1}{2}\right\rfloor.$$
Die primitiven Richtungen werden nach dem Winkel \(\theta=\operatorname{atan2}(y,x)\) sortiert. So erhält man eine kanonische Beschreibung des Randes: Wählt man den tiefsten Eckpunkt als Ursprung, können die Randkanten in nichtfallender Winkelreihenfolge gelesen werden. Ohne diese Normierung würde dasselbe Polygon über verschiedene zyklische Startpunkte oder verschiedene Darstellungen paralleler Kanten mehrfach gezählt.
Gespeichert wird der Zustand
$$ (X,Y,r), $$
wobei \((X,Y)\) die aktuelle Verschiebung vom gewählten Ursprung und \(r\) der verbleibende Umfang ist. Nutzt man die aktuelle primitive Richtung \((dx,dy)\) mit primitiver Länge \(\ell\) und Multiplizität \(g\ge 1\), dann gilt der Übergang
$$ (X,Y,r)\longrightarrow (X+g\,dx,\;Y+g\,dy,\;r-g\ell). $$
Das DP rät also nicht ganze Polygone auf einmal, sondern fügt einen kantenparallelen Block nach dem anderen in der festen Winkelreihenfolge hinzu.
Ein Übergang wird nur akzeptiert, wenn zwei geometrische Filter erfüllt sind.
Obere-Halbebene-Regel. Der Code fordert
$$Y_{\text{neu}}\ge 0.$$
Damit wird der tiefste Polygonpunkt als Ursprung festgelegt und verhindert, dass der partielle Weg unter ihn fällt. So zählt man genau einen kanonischen Vertreter statt vertikal verschobener oder zyklisch rotierter Duplikate.
Rückkehr-zum-Ursprung-Filter. Zusätzlich fordert der Code
$$X_{\text{neu}}^2+Y_{\text{neu}}^2\le r_{\text{neu}}^2.$$
Nach der Dreiecksungleichung ist ein Schluss unmöglich, wenn die euklidische Distanz zum Ursprung bereits größer als der verbleibende Umfang ist. Dieser Test entfernt sehr viele hoffnungslose Zustände.
Nach der Verarbeitung aller Richtungen entspricht jeder Zustand mit Verschiebung \((0,0)\) einem geschlossenen Weg aus zulässigen Kanten. Daher summiert das DP alle Zustände mit Ursprungsschlüssel über alle Restumfangsstufen.
Diese Rohsumme enthält aber noch zwei nichtpolygonale Artefakte:
Den leeren Weg. Der Anfangszustand am Ursprung zählt als triviale Schließung mit und muss entfernt werden.
Zweikanten-Rücksprünge. Für jede primitive Richtung der Länge \(\ell\) erzeugt eine Kante der Länge \(g\ell\) plus die entgegengesetzte Kante gleicher Länge einen geschlossenen degenerierten Linienzug mit Umfang \(2g\ell\), aber kein echtes Polygon. Die Anzahl solcher Fälle ist
$$\sum_{\text{primitive }v}\left\lfloor\frac{N}{2\ell(v)}\right\rfloor,$$
und wird durch \(2\) geteilt, weil jede Richtung und ihre Gegenrichtung beide in der Vektorliste vorkommen.
Genau deshalb lautet die Endformel
$$\text{Antwort}=\Bigl(\text{alle geschlossenen Zustände}\Bigr)-1-\text{diagonal}.$$
Die Implementierung prüft sich zunächst an
$$P(4)=1,\qquad P(30)=3655,\qquad P(60)=891045.$$
Für \(N=4\) ist das einzige Polygon das Einheitsquadrat, daher ist der erste Kontrollwert leicht zu sehen. Anschließend berechnet das Programm
$$P(120)=3600060866.$$
init_vectors erzeugt alle primitiven Ganzzahlvektoren mit ganzzahliger Norm bis \((N-1)/2\) und sortiert sie nach Winkel. Das Feld arr[r] ist eine Hash-Map erreichbarer Verschiebungen bei Restbudget \(r\). Gestartet wird am Ursprung mit Budget \(N\). Für jede Richtung probiert der Code alle zulässigen Multiplizitäten \(g\), wendet die beiden Pruning-Regeln an und trägt den Folgezustand in die Hash-Map mit kleinerem Restumfang ein. Am Ende werden alle Ursprungstreffer summiert und der leere Weg sowie die degenerierten Zweikanten-Fälle abgezogen.
Bezeichnet \(V\) die Anzahl primitiver Richtungen und \(S_r\) die Zahl erreichbarer Zustände bei Restumfang \(r\), so ist die Laufzeit näherungsweise
$$O\!\left(\sum_{v\in V}\sum_r S_r\,M_{v,r}\right),$$
wobei \(M_{v,r}\) die Zahl der noch passenden Multiplizitäten \(g\) ist. Der Speicherverbrauch ist die Gesamtgröße der Hash-Maps \(\texttt{arr}[0],\dots,\texttt{arr}[N]\). Der entscheidende Gewinn kommt aus dem geometrischen Pruning, insbesondere der Distanz-zum-Ursprung-Schranke.
Çevresi en fazla \(N\) olan ve tüm kenar uzunlukları tam sayı olan kafes poligonları saymak istiyoruz. Project Euler hedefi \(P(120)\)'dir. Kod poligonları doğrudan brute-force üretmez; bunun yerine izinli kenar yönlerinden başlayıp yer değiştirme ve kalan çevre üzerinde DP kurar.
Bir kenar vektörü \((x,y)\), ancak ve ancak
$$x^2+y^2=\ell^2$$
olduğu zaman tam sayı uzunluğa sahiptir. Aynı yönü tekrar tekrar üretmemek için kod yalnızca
$$\gcd(x,y)=1$$
olan primitive vektörleri tutar. Daha sonra bu yönlerin her pozitif katı \(g(x,y)\) serbesttir; uzunluk da \(g\ell\) olur. Gerçek bir poligonda hiçbir kenar toplam çevrenin yarısından uzun olamayacağı için
$$\ell \le \left\lfloor \frac{N-1}{2}\right\rfloor$$
sınırı yeterlidir.
Primitive yönler \(\theta=\operatorname{atan2}(y,x)\) açısına göre sıralanır. Bu, poligon sınırını kanonik bir biçimde tarif etmeyi sağlar: en düşük köşe orijin seçildiğinde, sınır kenarları artmayan değil artan açı sırasıyla okunabilir. Bu normalizasyon olmazsa aynı poligon farklı döngü başlangıçları veya paralel kenarların farklı gruplanmalarıyla tekrar tekrar sayılırdı.
Kodun tuttuğu durum şudur:
$$ (X,Y,r). $$
Burada \((X,Y)\), seçilen orijine göre mevcut net yer değiştirme; \(r\) ise kalan çevre bütçesidir. Sıradaki primitive yön \((dx,dy)\), primitive uzunluk \(\ell\) ve kat sayısı \(g\ge 1\) seçilirse geçiş
$$ (X,Y,r)\longrightarrow (X+g\,dx,\;Y+g\,dy,\;r-g\ell) $$
şeklindedir. Yani DP tek seferde tüm poligonu tahmin etmez; sabit açı sırasına göre bir kenar bloğu daha ekler.
Geçiş ancak iki geometrik filtre sağlanırsa kabul edilir.
Üst yarı-düzlem kuralı. Kod
$$Y_{\text{new}}\ge 0$$
ister. Böylece poligonun en düşük noktası orijin olarak sabitlenir ve kısmi yürüyüşün onun altına düşmesi yasaklanır. Sonuç olarak aynı sınırın düşey kaydırmaları veya döngüsel başlangıç değişimleri tek bir kanonik temsil altında toplanır.
Orijine dönebilme filtresi. Kod ayrıca
$$X_{\text{new}}^2+Y_{\text{new}}^2\le r_{\text{new}}^2$$
koşulunu arar. Üçgen eşitsizliğine göre, eğer orijine Öklid uzaklığı kalan çevreden büyükse kapanış artık imkansızdır. Bu test çok büyük sayıda umutsuz durumu erken atar.
Tüm yönler işlendiğinde, yer değiştirmesi \((0,0)\) olan her durum izinli kenarlardan oluşan kapalı bir yürüyüş verir. Bu yüzden DP, tüm kalan-çevre katmanlarında orijin anahtarına dönen durumları toplar.
Fakat bu ham toplam hâlâ iki yapay terim içerir:
Boş yürüyüş. Orijindeki başlangıç durumu da bir kapanış gibi görünür; bu yüzden çıkarılmalıdır.
İki kenarlı geri-dönüşler. Primitive uzunluğu \(\ell\) olan herhangi bir yön için, uzunluğu \(g\ell\) olan bir kenar ve aynı uzunlukta ters yönlü ikinci kenar, çevresi \(2g\ell\) olan kapalı ama dejenere bir çizgi parçası üretir; bu gerçek poligon değildir. Kod bunların sayısını
$$\sum_{\text{primitive }v}\left\lfloor\frac{N}{2\ell(v)}\right\rfloor$$
ile hesaplar ve her yön ile zıttı listede ayrı durduğu için \(2\)'ye böler.
Bu yüzden son formül
$$\text{cevap}=\Bigl(\text{tüm kapalı durumlar}\Bigr)-1-\text{diagonal}$$
şeklindedir.
Uygulama önce şu değerlerle kendini doğrular:
$$P(4)=1,\qquad P(30)=3655,\qquad P(60)=891045.$$
\(N=4\) için tek poligon birim karedir; bu yüzden ilk kontrol değeri görsel olarak kolaydır. Ardından program
$$P(120)=3600060866$$
sonucunu üretir.
init_vectors, normu \((N-1)/2\)'yi aşmayan tüm primitive tam sayı vektörlerini üretir ve açıya göre sıralar. arr[r] yapısı, kalan bütçesi \(r\) olan durumlarda erişilebilen yer değiştirmeleri tutan bir hash-map'tir. Başlangıçta yalnızca orijin ve bütçe \(N\) vardır. Her yön için kod tüm uygun \(g\) katsayılarını dener, iki budama kuralını uygular ve sonucu daha küçük kalan-çevre seviyesindeki hash-map'e ekler. Son aşamada orijine dönen tüm durumlar toplanır, sonra boş yol ile iki kenarlı dejenere kapanışlar çıkarılır.
Primitive yön sayısı \(V\), kalan-çevre seviyesi \(r\) için erişilebilen durum sayısı \(S_r\) ve yön \(v\) için denenebilen kat sayısı \(M_{v,r}\) olsun. Yaklaşık maliyet
$$O\!\left(\sum_{v\in V}\sum_r S_r\,M_{v,r}\right)$$
olur. Bellek kullanımı \(\texttt{arr}[0],\dots,\texttt{arr}[N]\) hash-map’lerinin toplam büyüklüğüdür. Asıl verim kazancı, özellikle orijine uzaklık filtresi olmak üzere geometrik budamadan gelir.
Queremos contar polígonos de rejilla cuyas longitudes de lado son enteras y cuyo perímetro no supera \(N\). Para Project Euler se necesita \(P(120)\). El código no enumera polígonos de forma directa; los construye a partir de direcciones de arista admisibles y hace programación dinámica sobre desplazamiento y perímetro restante.
Un vector de arista \((x,y)\) tiene longitud entera exactamente cuando
$$x^2+y^2=\ell^2.$$
Para no representar la misma dirección muchas veces, el código conserva solo vectores primitivos con
$$\gcd(x,y)=1.$$
Después permite cualquier múltiplo positivo \(g(x,y)\), cuya longitud es \(g\ell\). Como ninguna arista de un polígono real puede exceder la mitad del perímetro total, basta imponer
$$\ell \le \left\lfloor \frac{N-1}{2}\right\rfloor.$$
Las direcciones primitivas se ordenan por el ángulo \(\theta=\operatorname{atan2}(y,x)\). Eso da una descripción canónica del borde: si elegimos como origen el vértice más bajo, las aristas del contorno pueden leerse en orden angular no decreciente. Sin esta normalización, el mismo polígono aparecería muchas veces debido a distintos puntos iniciales cíclicos o distintas agrupaciones de aristas paralelas.
El estado almacenado es
$$ (X,Y,r), $$
donde \((X,Y)\) es el desplazamiento actual respecto del origen elegido y \(r\) es el presupuesto de perímetro restante. Si usamos la dirección primitiva actual \((dx,dy)\), de longitud primitiva \(\ell\), con multiplicidad \(g\ge 1\), el paso es
$$ (X,Y,r)\longrightarrow (X+g\,dx,\;Y+g\,dy,\;r-g\ell). $$
Así, el DP no adivina el polígono completo de una vez, sino que va añadiendo un bloque de arista cada vez siguiendo el orden angular.
Una transición solo se acepta si pasan dos filtros.
Regla del semiplano superior. El código exige
$$Y_{\text{nuevo}}\ge 0.$$
Eso fija el vértice más bajo como origen y prohíbe que el paseo parcial baje por debajo de él. Con ello se obtiene un único representante canónico, evitando traslaciones verticales o rotaciones cíclicas equivalentes del mismo borde.
Filtro de posibilidad de regreso. Además se exige
$$X_{\text{nuevo}}^2+Y_{\text{nuevo}}^2\le r_{\text{nuevo}}^2.$$
Por la desigualdad triangular, si la distancia euclídea al origen ya supera el perímetro restante, el cierre es imposible. Este test elimina muchísimos estados sin futuro.
Tras procesar todas las direcciones, cualquier estado con desplazamiento \((0,0)\) representa un paseo cerrado construido con aristas permitidas. Por eso el DP suma todas las apariciones de la clave del origen en todos los presupuestos restantes.
Pero ese conteo bruto incluye todavía dos artefactos no poligonales:
El paseo vacío. El estado inicial en el origen cuenta como un cierre trivial y debe restarse.
Los retrocesos de dos aristas. Para cualquier dirección primitiva de longitud \(\ell\), elegir una arista de longitud \(g\ell\) y luego la opuesta con la misma longitud da un segmento degenerado de perímetro \(2g\ell\), no un polígono genuino. El código cuenta esos casos mediante
$$\sum_{\text{primitiva }v}\left\lfloor\frac{N}{2\ell(v)}\right\rfloor,$$
y divide entre \(2\) porque cada dirección y su opuesta aparecen por separado en la lista.
Por eso la fórmula final es
$$\text{respuesta}=\Bigl(\text{todos los estados cerrados}\Bigr)-1-\text{diagonal}.$$
La implementación se valida primero con
$$P(4)=1,\qquad P(30)=3655,\qquad P(60)=891045.$$
Para \(N=4\), el único polígono es el cuadrado unidad, así que el primer control es fácil de visualizar. Después el programa obtiene
$$P(120)=3600060866.$$
init_vectors genera todos los vectores enteros primitivos con norma entera no superior a \((N-1)/2\), y luego los ordena por ángulo. La estructura arr[r] es una tabla hash de desplazamientos alcanzables con presupuesto restante \(r\). Se empieza en el origen con presupuesto \(N\). Para cada dirección, el código prueba todas las multiplicidades \(g\) posibles, aplica las dos reglas de poda y añade el estado resultante a la tabla hash del presupuesto menor. Al final suma todos los retornos al origen y resta el camino vacío y las clausuras degeneradas de dos aristas.
Si \(V\) es el número de direcciones primitivas, \(S_r\) el número de estados alcanzables con presupuesto restante \(r\), y \(M_{v,r}\) el número de multiplicidades válidas del vector \(v\), el coste es aproximadamente
$$O\!\left(\sum_{v\in V}\sum_r S_r\,M_{v,r}\right).$$
La memoria es el tamaño total de las tablas hash \(\texttt{arr}[0],\dots,\texttt{arr}[N]\). La mejora clave proviene de la poda geométrica, sobre todo de la cota de distancia al origen.
我们要统计周长不超过 \(N\)、且所有边长都是整数的格点多边形。Project Euler 需要的是 \(P(120)\)。代码并不是直接暴力生成多边形，而是先生成允许的边方向，再对“当前位移 + 剩余周长”做动态规划。
边向量 \((x,y)\) 只有在
$$x^2+y^2=\ell^2$$
时才有整数欧氏长度。为了不重复表示同一方向，代码只保留满足
$$\gcd(x,y)=1$$
的原始向量。之后允许任意正整数倍 \(g(x,y)\)，其长度就是 \(g\ell\)。由于真实多边形中任何一条边都不可能超过总周长的一半，所以只需考虑
$$\ell \le \left\lfloor \frac{N-1}{2}\right\rfloor.$$
所有原始方向按 \(\theta=\operatorname{atan2}(y,x)\) 排序。这样就得到一种规范表示：把多边形最低点选作原点后，边界方向可以按不下降的角度顺序读取。若没有这一步，同一个多边形会因为循环起点不同、或平行边合并方式不同而被重复计算。
程序保存的状态是
$$ (X,Y,r), $$
其中 \((X,Y)\) 是相对所选原点的当前位移，\(r\) 是剩余周长预算。若当前原始方向为 \((dx,dy)\)、原始长度为 \(\ell\)，并选择倍数 \(g\ge 1\)，则转移为
$$ (X,Y,r)\longrightarrow (X+g\,dx,\;Y+g\,dy,\;r-g\ell). $$
也就是说，DP 不是一次猜出整个多边形，而是按固定角度顺序一段一段地加入边。
一个转移只有在通过两条几何过滤后才会保留。
上半平面规则。 代码要求
$$Y_{\text{new}}\ge 0.$$
这相当于把最低顶点固定为原点，并禁止部分路径掉到它的下方。这样就只保留一个规范代表，不会把同一条边界的垂直平移或循环重标记重复计算。
可回原点规则。 代码还要求
$$X_{\text{new}}^2+Y_{\text{new}}^2\le r_{\text{new}}^2.$$
根据三角不等式，如果当前位置到原点的欧氏距离已经大于剩余周长，那么无论如何都不可能闭合。这条规则能删掉大量注定失败的状态。
所有方向都处理完后，任何位移为 \((0,0)\) 的状态都对应一条由允许边组成的闭合路径。因此程序会把所有剩余周长层里回到原点的状态相加。
但这个原始和仍然包含两个不是“真正多边形”的对象：
空路径。 初始原点状态本身会被算成一次闭合，因此必须减去。
两边往返的退化情形。 对任一原始方向，若先走长度 \(g\ell\) 的边，再走同长度反向边，就得到周长 \(2g\ell\) 的闭合线段，而不是合法多边形。代码用
$$\sum_{\text{primitive }v}\left\lfloor\frac{N}{2\ell(v)}\right\rfloor$$
来统计这种对象，再除以 \(2\)，因为方向与反方向都在方向表中出现一次。
因此最终公式是
$$\text{answer}=\Bigl(\text{all closed states}\Bigr)-1-\text{diagonal}.$$
程序先验证
$$P(4)=1,\qquad P(30)=3655,\qquad P(60)=891045.$$
其中 \(P(4)=1\) 很直观，因为周长 \(4\) 时唯一的多边形就是单位正方形。最终目标值为
$$P(120)=3600060866.$$
init_vectors 生成所有整数范数不超过 \((N-1)/2\) 的原始整向量，并按极角排序。结构 arr[r] 是“剩余预算为 \(r\) 时可达位移”的哈希表。起始状态是预算 \(N\) 下的原点。对每个方向，程序尝试所有可行倍数 \(g\)，应用两条剪枝规则，把结果加入更小预算层的哈希表。最后把所有原点闭合状态求和，再减去空路径和两边退化闭合。
若原始方向数为 \(V\)，预算层 \(r\) 上的可达状态数为 \(S_r\)，方向 \(v\) 在层 \(r\) 可尝试的倍数数为 \(M_{v,r}\)，则总复杂度近似为
$$O\!\left(\sum_{v\in V}\sum_r S_r\,M_{v,r}\right).$$
空间复杂度是所有哈希表 \(\texttt{arr}[0],\dots,\texttt{arr}[N]\) 的总大小。效率提升的关键主要来自几何剪枝，尤其是“剩余周长必须足以回原点”这一条件。
Нужно посчитать решётчатые многоугольники, у которых все длины рёбер целые и периметр не превосходит \(N\). Для задачи Project Euler требуется \(P(120)\). Код не перебирает многоугольники напрямую; он строит их из допустимых направлений рёбер и применяет динамику по смещению и оставшемуся периметру.
Вектор ребра \((x,y)\) имеет целую длину тогда и только тогда, когда
$$x^2+y^2=\ell^2.$$
Чтобы не хранить одну и ту же направленность много раз, код оставляет только примитивные векторы с
$$\gcd(x,y)=1.$$
После этого разрешаются любые положительные кратности \(g(x,y)\), длина которых равна \(g\ell\). Поскольку в настоящем многоугольнике ни одно ребро не может быть длиннее половины полного периметра, достаточно рассматривать
$$\ell \le \left\lfloor \frac{N-1}{2}\right\rfloor.$$
Все примитивные направления сортируются по углу \(\theta=\operatorname{atan2}(y,x)\). Это создаёт каноническое описание границы: если выбрать нижнюю вершину многоугольника как начало координат, то рёбра границы можно читать в неубывающем порядке углов. Без такой нормировки один и тот же многоугольник появлялся бы много раз из-за разных циклических стартов или разных способов объединения параллельных рёбер.
Хранимое состояние имеет вид
$$ (X,Y,r), $$
где \((X,Y)\) — текущее смещение от выбранного начала, а \(r\) — оставшийся бюджет периметра. Если текущий примитивный вектор равен \((dx,dy)\), его примитивная длина равна \(\ell\), а выбранная кратность равна \(g\ge 1\), то переход таков:
$$ (X,Y,r)\longrightarrow (X+g\,dx,\;Y+g\,dy,\;r-g\ell). $$
То есть DP не угадывает целый многоугольник за раз, а добавляет один углово упорядоченный блок рёбер за другим.
Переход принимается только при выполнении двух условий.
Правило верхней полуплоскости. Код требует
$$Y_{\text{new}}\ge 0.$$
Это фиксирует нижнюю вершину многоугольника как начало координат и запрещает частичному пути уходить ниже неё. Благодаря этому считается один канонический представитель вместо вертикально сдвинутых или циклически переименованных копий одной и той же границы.
Фильтр возможности возврата. Также код требует
$$X_{\text{new}}^2+Y_{\text{new}}^2\le r_{\text{new}}^2.$$
По неравенству треугольника, если евклидово расстояние до начала уже больше оставшегося периметра, замыкание невозможно. Этот тест отбрасывает огромное число безнадёжных состояний.
После обработки всех направлений любой статус со смещением \((0,0)\) соответствует замкнутому пути из допустимых рёбер. Поэтому программа суммирует все состояния с ключом начала координат на всех уровнях остатка периметра.
Но в эту «сырую» сумму входят ещё два неполигональных объекта:
Пустой путь. Начальное состояние в начале координат считается тривиальным замыканием и должно быть вычтено.
Двухрёберные возвраты. Для любого примитивного направления длины \(\ell\), если пройти ребро длины \(g\ell\), а потом ровно такое же в противоположную сторону, получится вырожденный отрезок периметра \(2g\ell\), а не настоящий многоугольник. Их число код оценивает формулой
$$\sum_{\text{primitive }v}\left\lfloor\frac{N}{2\ell(v)}\right\rfloor,$$
после чего делит на \(2\), потому что в списке направлений присутствуют и вектор, и его противоположный.
Поэтому окончательная формула имеет вид
$$\text{answer}=\Bigl(\text{all closed states}\Bigr)-1-\text{diagonal}.$$
Реализация сначала проверяет себя на значениях
$$P(4)=1,\qquad P(30)=3655,\qquad P(60)=891045.$$
Для \(N=4\) единственный многоугольник — единичный квадрат, поэтому первый контроль легко увидеть. После этого программа вычисляет
$$P(120)=3600060866.$$
init_vectors генерирует все примитивные целочисленные векторы с целой нормой не больше \((N-1)/2\) и сортирует их по углу. Структура arr[r] — это хеш-таблица достижимых смещений при остатке периметра \(r\). Старт происходит из начала координат при бюджете \(N\). Для каждого направления код перебирает все допустимые кратности \(g\), применяет два фильтра и заносит результат в таблицу с меньшим остатком. В финале суммируются все возвраты в начало, после чего вычитаются пустой путь и вырожденные двухрёберные замыкания.
Если \(V\) — число примитивных направлений, \(S_r\) — число достижимых состояний при остатке \(r\), а \(M_{v,r}\) — число допустимых кратностей для направления \(v\), то оценка времени равна
$$O\!\left(\sum_{v\in V}\sum_r S_r\,M_{v,r}\right).$$
Память — это общий объём хеш-таблиц \(\texttt{arr}[0],\dots,\texttt{arr}[N]\). Ключевое ускорение даёт геометрическое pruning, особенно ограничение по расстоянию до начала.
نريد عدّ المضلعات الشبكية التي لا يتجاوز محيطها \(N\) وتكون جميع أطوال أضلاعها أعدادًا صحيحة. في مسألة Project Euler نحتاج إلى \(P(120)\). لا يولّد الكود المضلعات مباشرة بطريقة brute force، بل يبنيها من اتجاهات أضلاع مسموح بها ثم يطبق برمجة ديناميكية على الإزاحة والمحيط المتبقي.
يكون متجه الضلع \((x,y)\) ذا طول صحيح إذا وفقط إذا تحقق
$$x^2+y^2=\ell^2.$$
ولتجنب تمثيل الاتجاه نفسه مرات كثيرة، يحتفظ الكود فقط بالمتجهات الأولية التي تحقق
$$\gcd(x,y)=1.$$
ثم يسمح بعد ذلك بأي مضاعف موجب \(g(x,y)\)، ويكون طوله \(g\ell\). وبما أن أي ضلع في مضلع حقيقي لا يمكن أن يتجاوز نصف المحيط الكلي، فإن الشرط الكافي هو
$$\ell \le \left\lfloor \frac{N-1}{2}\right\rfloor.$$
تُرتَّب جميع الاتجاهات الأولية حسب الزاوية \(\theta=\operatorname{atan2}(y,x)\). وهذا يعطي تمثيلًا قياسيًا لحدود المضلع: إذا اخترنا أدنى رأس بوصفه الأصل، أمكن قراءة أضلاع الحد بترتيب زاوي غير تنازلي. ومن دون هذه الخطوة سيظهر المضلع نفسه مرات عديدة بسبب تغيّر نقطة البداية الدورية أو بسبب طرق مختلفة لدمج الأضلاع المتوازية.
الحالة المخزنة هي
$$ (X,Y,r), $$
حيث تمثل \((X,Y)\) الإزاحة الحالية بالنسبة إلى الأصل المختار، ويمثل \(r\) ميزانية المحيط المتبقية. إذا كان الاتجاه الأولي الحالي هو \((dx,dy)\)، وطوله الأولي \(\ell\)، واخترنا مضاعفًا \(g\ge 1\)، فإن الانتقال يكون
$$ (X,Y,r)\longrightarrow (X+g\,dx,\;Y+g\,dy,\;r-g\ell). $$
أي إن البرمجة الديناميكية لا تخمّن المضلع كاملًا دفعة واحدة، بل تضيف كتلة ضلع واحدة في كل مرة وفق الترتيب الزاوي الثابت.
لا يُقبل الانتقال إلا إذا نجح في فلترين هندسيين.
قاعدة النصف العلوي. يشترط الكود
$$Y_{\text{new}}\ge 0.$$
وهذا يعني تثبيت أدنى رأس في المضلع بوصفه الأصل، ومنع المسار الجزئي من النزول تحته. بهذه الطريقة نحصل على ممثل قياسي واحد بدلًا من عدّ النسخ المزاحة رأسيًا أو المعاد تدوير نقطة بدايتها دوريًا.
فلتر إمكانية الرجوع إلى الأصل. كما يشترط الكود
$$X_{\text{new}}^2+Y_{\text{new}}^2\le r_{\text{new}}^2.$$
فبحسب متباينة المثلث، إذا صارت المسافة الإقليدية إلى الأصل أكبر من المحيط المتبقي، فلا يمكن إغلاق المسار. هذا الاختبار يحذف عددًا ضخمًا من الحالات الميؤوس منها.
بعد معالجة جميع الاتجاهات، فإن كل حالة ذات إزاحة \((0,0)\) تمثل مسارًا مغلقًا مكوّنًا من أضلاع مسموح بها. لذلك يجمع البرنامج جميع الحالات التي تعود إلى مفتاح الأصل عبر كل مستويات المحيط المتبقي.
لكن هذا العد الخام ما زال يحتوي على جسمين غير صالحين بوصفهما مضلعين:
المسار الفارغ. الحالة الابتدائية في الأصل تُحسب كإغلاق تافه، لذلك يجب طرحها.
الرجوع ذو الضلعين. لأي اتجاه أولي طوله \(\ell\)، إذا أخذنا ضلعًا بطول \(g\ell\) ثم ضلعًا مساويًا له في الاتجاه المعاكس، نحصل على قطعة مستقيمة مندرجة ذات محيط \(2g\ell\)، وليست مضلعًا حقيقيًا. يحسب الكود هذه الحالات عبر
$$\sum_{\text{primitive }v}\left\lfloor\frac{N}{2\ell(v)}\right\rfloor,$$
ثم يقسم على \(2\) لأن كل اتجاه وضده يظهران في قائمة الاتجاهات.
ولهذا تكون الصيغة النهائية
$$\text{answer}=\Bigl(\text{all closed states}\Bigr)-1-\text{diagonal}.$$
يتحقق التنفيذ أولًا من القيم
$$P(4)=1,\qquad P(30)=3655,\qquad P(60)=891045.$$
فعند \(N=4\) لا يوجد سوى مربع الوحدة، ولذلك يكون أول checkpoint واضحًا بصريًا. ثم ينتج البرنامج
$$P(120)=3600060866.$$
تقوم الدالة init_vectors بتوليد جميع المتجهات الصحيحة الأولية ذات الطول الصحيح حتى \((N-1)/2\)، ثم ترتبها حسب الزاوية. والبنية arr[r] هي جدول تجزئة للإزاحات الممكنة عند بقاء ميزانية محيط مقدارها \(r\). تبدأ العملية من الأصل مع ميزانية \(N\). ولكل اتجاه، يجرّب الكود جميع المضاعفات الممكنة \(g\)، ويطبق قاعدتي الحذف المبكر، ثم يضيف الحالة الناتجة إلى الجدول الموافق للميزانية الأصغر. وفي النهاية يجمع جميع الإغلاقات عند الأصل، ثم يطرح المسار الفارغ والإغلاقات المتدهورة ذات الضلعين.
إذا كان \(V\) هو عدد الاتجاهات الأولية، و\(S_r\) هو عدد الحالات القابلة للوصول عند ميزانية متبقية \(r\)، و\(M_{v,r}\) هو عدد المضاعفات المسموح بها للاتجاه \(v\)، فإن التعقيد التقريبي هو
$$O\!\left(\sum_{v\in V}\sum_r S_r\,M_{v,r}\right).$$
أما الذاكرة فهي الحجم الكلي لجداول التجزئة \(\texttt{arr}[0],\dots,\texttt{arr}[N]\). وأهم سبب للفعالية هو الحذف الهندسي المبكر، وخصوصًا شرط أن يكون المحيط المتبقي كافيًا للعودة إلى الأصل.