Let \(A(N)\) be the minimum area of a convex lattice polygon with \(N\) edges. The supplied C++, Python, and Java implementations solve the target case \(N\equiv 0 \pmod{4}\) by writing \(N=4Q\), constructing one monotone quarter-chain, and recovering the full polygon by symmetry. The search is therefore over ordered primitive edge directions and compact area summaries rather than over polygons themselves.
The implementation organizes the polygon as four reflected copies of a quarter construction. That reduces the problem to a structured optimization on primitive lattice directions.
Write
$$N=4Q.$$
The implemented strategy treats one quarter of the optimal polygon as a convex monotone chain. A steep half-chain runs from the vertical boundary toward the diagonal, a mirrored half-chain finishes that quadrant, and reflections across the coordinate axes produce the remaining three quadrants.
Inside the steep half-chain, every nontrivial edge direction is represented by a primitive lattice vector
$$\gcd(x,y)=1,\qquad 1\le x<y.$$
Sorting these vectors by slope \(x/y\) enforces the monotone turning order needed for convexity. The program therefore works with primitive directions in increasing slope order.
A quarter-chain has exactly \(Q\) edges, but its two extreme directions are fixed by the construction, so only \(Q-2\) internal primitive directions can be chosen freely. For a primitive vector \((x,y)\), the implementations precompute
$$\Pi(x,y)=\#\left\{(u,v):1\le u\le x,\ 1\le v\le y,\ u<v,\ \gcd(u,v)=1\right\}.$$
This is the number of primitive directions in the southwest rectangle up to \((x,y)\). If
$$\Pi(x,y)>Q-2,$$
then \((x,y)\) is already too deep in that ordered set to fit into a quarter-chain with only \(Q\) total edges, so it is discarded immediately. This pruning step is why the candidate list stays manageable even when \(Q\) is much larger than the visible number of states in the later dynamic program.
Suppose the currently chosen internal directions in one steep half-chain are
$$ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k), $$
already sorted by slope. The implementations summarize this entire partial chain by two quantities:
$$\Sigma_k=1+2\sum_{i=1}^{k} y_i,$$
$$\Lambda_k=2\sum_{j=1}^{k} x_j\left(1+y_j+2\sum_{i<j} y_i\right).$$
The base state is
$$ (\Sigma,\Lambda)=(1,0). $$
Appending a new primitive direction \((x,y)\) updates the summary by
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y).$$
This recurrence is the core of the dynamic program. The important point is that every future contribution of the already chosen directions is mediated only through \(\Sigma\) and \(\Lambda\), so no finer geometric description is needed once a state has been compressed into this pair.
For each possible chain length, many reachable states are useless. If two states have the same \(\Sigma\), only the one with smaller \(\Lambda\) can ever help. The implementations go further and keep only the lower convex envelope of the reachable \((\Sigma,\Lambda)\) points.
The reason is visible in the final merge formula. If the opposite half of the quarter contributes \((\Sigma_1,\Lambda_1)\), then using a state \((\Sigma_0,\Lambda_0)\) on the current side leads to
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2.$$
For fixed \((\Sigma_1,\Lambda_1)\), this is
$$\mathcal{V}=\bigl(\Lambda_0+(\Sigma_1+2)\Sigma_0\bigr)+C,$$
which is a linear functional of \((\Sigma_0,\Lambda_0)\) with positive slope \(\Sigma_1+2\). Therefore any state lying above the lower convex envelope can never be optimal for any later merge, and the cross-product test used in the implementations deletes exactly those states.
The algorithm stores one filtered frontier for every possible number of quarter-edges. If one side of the quarter uses \(\ell\) edges and the other side uses \(Q-\ell\) edges, every pair of frontier states produces the candidate area
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2.$$
The minimum is taken over all splits
$$1\le \ell < Q$$
and over all pairs of filtered states in the corresponding two frontiers. The special case \(Q=1\), which means \(N=4\), is handled directly and gives area \(1\).
Here \(Q=2\). Since a quarter-chain has only \(Q-2=0\) internal slots, no extra primitive direction can be inserted. The only stored frontier state on each side is still the base state
$$ (\Sigma,\Lambda)=(1,0). $$
The only possible split is \(1+1\), so the candidate value is
$$A(8)=0+0+(1+2)(1+2)-2=9-2=7.$$
This matches the checkpoint built into the implementations.
The C++, Python, and Java implementations first reject inputs that are not multiples of \(4\), then set \(Q=N/4\). They enumerate primitive first-octant directions, count how many smaller rectangle-contained primitive directions each one has, and keep only those that satisfy the cutoff from Step 2. The surviving directions are then sorted by slope.
Next, the implementation keeps one frontier for each possible quarter-length. Starting from the base frontier \((1,0)\), every candidate direction is appended to every existing frontier of smaller length, creating new summarized states through the recurrence
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y).$$
After each batch of insertions, the frontier is merged with the previously known states of that length and filtered back down to its lower convex envelope.
After all candidates have been processed, complementary frontiers of lengths \(\ell\) and \(Q-\ell\) are joined. For every pair, the program evaluates
$$\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2$$
and keeps the smallest result. The C++ implementation also checks several known small values before evaluating the target case.
Let \(E\) be the number of retained primitive directions after the rectangle cutoff, and let \(H_r\) be the size of the filtered frontier for quarter-length \(r\). Building the primitive table and the two-dimensional prefix-count table costs \(O(Q^2)\) memory. The gcd tests and the final slope sort contribute \(O(Q^2\log Q+E\log E)\) time.
The dynamic-programming phase generates roughly
$$O\left(E\sum_{r=1}^{Q-1} H_r\right)$$
state extensions, followed by linear-time hull merges on the produced frontier lists. The final meet-in-the-middle stage costs
$$O\left(\sum_{r=1}^{Q-1} H_r H_{Q-r}\right).$$
So the practical running time is controlled far more by the filtered frontier sizes than by the astronomically large number of convex lattice polygons one might try to enumerate directly. Total memory usage is
$$O\left(Q^2+\sum_{r=1}^{Q} H_r\right).$$
Sei \(A(N)\) die minimale Fläche eines konvexen Gitterpolygons mit \(N\) Kanten. Die vorliegenden Implementierungen behandeln den Zielfall \(N\equiv 0 \pmod{4}\), indem sie \(N=4Q\) schreiben, eine monotone Viertelkette konstruieren und das gesamte Polygon anschließend durch Symmetrie rekonstruieren. Gesucht wird also nicht direkt unter allen Polygonen, sondern unter geordneten primitiven Kantenrichtungen mit kompakten Flächensummen.
Die Implementierung organisiert das Polygon als vier gespiegelte Kopien einer Viertelkonstruktion. Dadurch wird die Aufgabe auf eine strukturierte Optimierung über primitive Gitterrichtungen reduziert.
Schreibe
$$N=4Q.$$
Die implementierte Strategie betrachtet ein Viertel des optimalen Polygons als konvexe monotone Kette. Eine steile Halbkette läuft von der vertikalen Randrichtung zur Diagonale, eine gespiegelte Halbkette vervollständigt dieses Quadrantenstück, und Spiegelungen an den Koordinatenachsen liefern die übrigen drei Quadranten.
Innerhalb der steilen Halbkette wird jede nichttriviale Kantenrichtung durch einen primitiven Gittervektor beschrieben:
$$\gcd(x,y)=1,\qquad 1\le x<y.$$
Diese Vektoren werden nach der Steigung \(x/y\) sortiert. Genau diese Reihenfolge erzwingt die monotone Drehrichtung, die für Konvexität benötigt wird.
Eine Viertelkette besitzt genau \(Q\) Kanten, aber ihre beiden Extremrichtungen sind durch die Konstruktion bereits festgelegt. Frei wählbar sind also nur \(Q-2\) innere primitive Richtungen. Für einen primitiven Vektor \((x,y)\) berechnen die Implementierungen
$$\Pi(x,y)=\#\left\{(u,v):1\le u\le x,\ 1\le v\le y,\ u<v,\ \gcd(u,v)=1\right\}.$$
Das ist die Anzahl primitiver Richtungen im südwestlichen Rechteck bis \((x,y)\). Gilt
$$\Pi(x,y)>Q-2,$$
dann liegt \((x,y)\) in dieser geordneten Menge bereits zu weit hinten, um noch in eine Viertelkette mit nur \(Q\) Gesamtkanten zu passen. Solche Richtungen werden daher sofort verworfen. Dieses frühe Abschneiden hält die Kandidatenmenge klein.
Seien die bisher gewählten inneren Richtungen einer steilen Halbkette
$$ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k), $$
bereits nach Steigung sortiert. Die Implementierungen fassen diese ganze Teilkette durch zwei Größen zusammen:
$$\Sigma_k=1+2\sum_{i=1}^{k} y_i,$$
$$\Lambda_k=2\sum_{j=1}^{k} x_j\left(1+y_j+2\sum_{i<j} y_i\right).$$
Der Anfangszustand lautet
$$ (\Sigma,\Lambda)=(1,0). $$
Wird ein neuer primitiver Vektor \((x,y)\) angehängt, dann gilt die Rekursion
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y).$$
Das ist der Kern der dynamischen Programmierung. Entscheidend ist, dass alle späteren Beiträge der bereits gewählten Richtungen nur noch über \(\Sigma\) und \(\Lambda\) in Erscheinung treten. Eine feinere Beschreibung der Geometrie wird für die Fortsetzung nicht mehr benötigt.
Für jede mögliche Kettenlänge sind viele erreichbare Zustände nutzlos. Haben zwei Zustände denselben Wert von \(\Sigma\), so kann nur der kleinere \(\Lambda\)-Wert jemals optimal sein. Die Implementierungen gehen noch weiter und behalten nur die untere konvexe Hülle der erreichbaren Punkte \((\Sigma,\Lambda)\).
Der Grund steht in der Endformel für das Zusammenfügen. Liefert die gegenüberliegende Hälfte den Zustand \((\Sigma_1,\Lambda_1)\), dann führt der aktuelle Zustand \((\Sigma_0,\Lambda_0)\) zu
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2.$$
Für festes \((\Sigma_1,\Lambda_1)\) ist das gleich
$$\mathcal{V}=\bigl(\Lambda_0+(\Sigma_1+2)\Sigma_0\bigr)+C,$$
also ein lineares Funktional der linken Punkte mit positiver Steigung \(\Sigma_1+2\). Jeder Punkt oberhalb der unteren konvexen Hülle kann deshalb in keinem späteren Merge optimal werden und wird per Kreuzprodukttest entfernt.
Der Algorithmus speichert für jede mögliche Anzahl von Viertelkanten genau eine gefilterte Frontier. Verwendet eine Seite des Viertels \(\ell\) Kanten und die andere \(Q-\ell\) Kanten, dann liefert jedes Paar von Frontier-Zuständen die Kandidatenfläche
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2.$$
Das Minimum wird über alle Aufteilungen
$$1\le \ell < Q$$
und über alle Zustandspaare der beiden zugehörigen Frontiers genommen. Der Spezialfall \(Q=1\), also \(N=4\), wird direkt behandelt und ergibt die Fläche \(1\).
Hier ist \(Q=2\). Da eine Viertelkette nur \(Q-2=0\) innere Plätze besitzt, kann keine zusätzliche primitive Richtung eingefügt werden. Auf jeder Seite bleibt also nur der Anfangszustand
$$ (\Sigma,\Lambda)=(1,0). $$
Die einzige mögliche Aufteilung ist \(1+1\), also
$$A(8)=0+0+(1+2)(1+2)-2=9-2=7.$$
Genau dieser Wert erscheint auch als Kontrollpunkt in den Implementierungen.
Die C++-, Python- und Java-Implementierungen verwerfen zuerst alle Eingaben, die keine Vielfachen von \(4\) sind, und setzen dann \(Q=N/4\). Danach werden primitive Richtungen im ersten Oktanten erzeugt, nachgezählt, wie viele kleinere primitive Richtungen in ihrem umschließenden Rechteck liegen, und nur die Richtungen mit dem Grenzwert aus Schritt 2 behalten. Anschließend werden die überlebenden Richtungen nach ihrer Steigung sortiert.
Danach verwaltet die Implementierung für jede mögliche Viertellänge eine Frontier. Beginnend mit dem Startzustand \((1,0)\) wird jede Kandidatenrichtung an alle bereits vorhandenen Frontiers kleinerer Länge angehängt, wodurch über
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y)$$
neue komprimierte Zustände entstehen. Nach jedem Einfügeschritt wird mit der vorhandenen Frontier derselben Länge zusammengeführt und sofort wieder auf die untere konvexe Hülle zurückgefiltert.
Am Ende werden komplementäre Frontiers der Längen \(\ell\) und \(Q-\ell\) gepaart. Für jedes Paar wertet das Programm
$$\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2$$
aus und merkt sich das kleinste Ergebnis. Die C++-Variante prüft außerdem einige bekannte kleinere Werte, bevor sie den Zielfall berechnet.
Sei \(E\) die Zahl der nach dem Rechteckkriterium verbleibenden primitiven Richtungen, und sei \(H_r\) die Größe der gefilterten Frontier für Viertellänge \(r\). Der Aufbau der Primitivtabelle und der zweidimensionalen Präfixzählung benötigt \(O(Q^2)\) Speicher. Die ggT-Tests und das abschließende Sortieren nach Steigung kosten insgesamt \(O(Q^2\log Q+E\log E)\) Zeit.
Die dynamische Programmierung erzeugt ungefähr
$$O\left(E\sum_{r=1}^{Q-1} H_r\right)$$
Zustandserweiterungen; danach folgen lineare Hüllen-Merges auf den jeweils erzeugten Listen. Das abschließende Meet-in-the-Middle kostet
$$O\left(\sum_{r=1}^{Q-1} H_r H_{Q-r}\right).$$
Praktisch wird die Laufzeit daher viel stärker durch die Größen der gefilterten Frontiers bestimmt als durch die riesige Menge aller konvexen Gitterpolygone, die ein naiver Ansatz betrachten müsste. Der gesamte Speicherbedarf beträgt
$$O\left(Q^2+\sum_{r=1}^{Q} H_r\right).$$
\(A(N)\), \(N\) kenarlı bir konveks kafes poligonunun alabileceği en küçük alan olsun. Verilen C++, Python ve Java uygulamaları hedef durum olan \(N\equiv 0 \pmod{4}\) için \(N=4Q\) yazıp tek bir çeyrek zinciri kuruyor, ardından tüm poligonu simetriyle tamamlıyor. Böylece arama doğrudan poligonlar üzerinde değil, sıralı ilkel kenar yönleri ve onların alan katkılarını özetleyen durumlar üzerinde yapılıyor.
Uygulama poligonu, tek bir çeyrek yapının dört yansımadan oluşan kopyası gibi ele alır. Bu da problemi ilkel kafes yönleri üzerinde düzenli bir optimizasyona indirger.
Şunu yazalım:
$$N=4Q.$$
Uygulanan stratejide optimal poligonun bir çeyreği, konveks ve monoton bir zincir olarak modellenir. Dik eksenden köşegene giden dik bir yarım zincir alınır, bunun köşegene göre yansıması aynı çeyreği tamamlar, sonra koordinat eksenlerine göre yansımalarla diğer üç çeyrek elde edilir.
Bu dik yarım zincirdeki her gayri trivial kenar yönü, ilkel bir kafes vektörüyle temsil edilir:
$$\gcd(x,y)=1,\qquad 1\le x<y.$$
Bu vektörleri \(x/y\) eğimine göre sıralamak, konvekslik için gerekli olan monoton dönme sırasını verir. Kod bu nedenle yönleri artan eğim sırasıyla işler.
Bir çeyrek zincirde toplam \(Q\) kenar vardır; fakat iki uç yön zaten yapı tarafından sabitlenmiştir. Dolayısıyla serbestçe seçilebilecek iç ilkel yön sayısı yalnızca \(Q-2\)'dir. Uygulamalar, her ilkel \((x,y)\) vektörü için
$$\Pi(x,y)=\#\left\{(u,v):1\le u\le x,\ 1\le v\le y,\ u<v,\ \gcd(u,v)=1\right\}$$
değerini hesaplar. Bu, \((x,y)\)'ye kadar olan güneybatı dikdörtgenindeki ilkel yönlerin sayısıdır. Eğer
$$\Pi(x,y)>Q-2,$$
ise bu yön, yalnızca \(Q\) kenarlı bir çeyrek zincire yerleşemeyecek kadar derinde kalır ve daha dinamik programlama başlamadan elenir. Bu erken budama, aday listesini yönetilebilir boyutta tutar.
Bir dik yarım zincirde şimdiye kadar seçilmiş iç yönler
$$ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k) $$
olsun ve bunlar zaten eğime göre sıralanmış olsun. Uygulamalar bu kısmi zinciri iki büyüklükle özetler:
$$\Sigma_k=1+2\sum_{i=1}^{k} y_i,$$
$$\Lambda_k=2\sum_{j=1}^{k} x_j\left(1+y_j+2\sum_{i<j} y_i\right).$$
Başlangıç durumu
$$ (\Sigma,\Lambda)=(1,0) $$
şeklindedir. Yeni bir \((x,y)\) vektörü eklendiğinde özet şu şekilde güncellenir:
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y).$$
Dinamik programlamanın özü bu bağıntıdır. Önemli nokta şudur: Daha önce seçilen kenarların gelecekte yapacağı tüm katkılar yalnızca \(\Sigma\) ve \(\Lambda\) üzerinden taşınır. Yani daha ayrıntılı bir geometrik durum saklamaya gerek yoktur.
Her olası zincir uzunluğu için erişilebilir durumların çoğu işe yaramaz. İki durumun \(\Sigma\) değeri aynıysa sadece daha küçük \(\Lambda\) değerine sahip olan yararlı olabilir. Uygulamalar bunun da ötesine geçip erişilebilir \((\Sigma,\Lambda)\) noktalarının yalnızca alt konveks zarfını tutar.
Bunun nedeni son birleştirme formülünde görülür. Karşı yarı \((\Sigma_1,\Lambda_1)\) katkısını veriyorsa, mevcut taraftaki \((\Sigma_0,\Lambda_0)\) durumu için toplam aday değer
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2$$
olur. Sabit \((\Sigma_1,\Lambda_1)\) için bu ifade
$$\mathcal{V}=\bigl(\Lambda_0+(\Sigma_1+2)\Sigma_0\bigr)+C$$
şeklinde, pozitif eğimli bir doğrusal fonksiyondur. Dolayısıyla alt konveks zarfın üstünde kalan hiçbir nokta daha sonra optimal olamaz; uygulamalardaki çapraz çarpım testi tam olarak bu noktaları siler.
Algoritma, çeyrek içindeki her olası kenar sayısı için bir filtrelenmiş sınır kümesi saklar. Çeyreğin bir tarafı \(\ell\) kenar, öbür tarafı \(Q-\ell\) kenar kullanıyorsa, bu iki sınır kümesindeki her durum çifti
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2$$
alan adayını üretir. En küçük değer tüm
$$1\le \ell < Q$$
bölmeleri ve ilgili tüm durum çiftleri üzerinde alınır. \(Q=1\), yani \(N=4\), özel durumu doğrudan ele alınır ve alan \(1\) çıkar.
Burada \(Q=2\) olur. Bir çeyrek zincirde \(Q-2=0\) iç yuva bulunduğundan ek bir ilkel yön eklenemez. Her iki tarafta da elde kalan tek durum başlangıç durumudur:
$$ (\Sigma,\Lambda)=(1,0). $$
Tek mümkün bölme \(1+1\) olduğundan
$$A(8)=0+0+(1+2)(1+2)-2=9-2=7$$
elde edilir. Bu değer, uygulamalardaki kontrol sonucu ile aynıdır.
C++, Python ve Java uygulamaları önce \(4\)'ün katı olmayan girdileri reddeder, sonra \(Q=N/4\) alır. Ardından birinci oktanttaki ilkel yönleri üretir, her yön için onu kapsayan dikdörtgen içinde kaç tane daha küçük ilkel yön bulunduğunu hesaplar ve yalnızca Adım 2'deki eşiği geçenleri tutar. Sonra bu yönler eğime göre sıralanır.
Daha sonra uygulama, her olası çeyrek uzunluğu için bir sınır kümesi tutar. Başlangıç durumu \((1,0)\)'dan başlayarak her aday yön, daha kısa tüm mevcut sınırlara eklenir ve
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y)$$
bağıntısıyla yeni özet durumlar üretilir. Her eklemeden sonra aynı uzunluktaki önceki sınır kümesiyle birleştirme yapılır ve sonuç yeniden alt konveks zarfa indirgenir.
Tüm adaylar işlendiğinde, uzunlukları \(\ell\) ile \(Q-\ell\) olan tamamlayıcı sınır kümeleri eşleştirilir. Her çift için program
$$\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2$$
ifadesini hesaplar ve en küçüğünü saklar. C++ sürümü ayrıca hedef girdiyi çözmeden önce bazı bilinen küçük değerleri de doğrular.
\(E\), dikdörtgen kesiminden sonra kalan ilkel yön sayısı olsun; \(H_r\) ise çeyrek uzunluğu \(r\) için filtrelenmiş sınır büyüklüğü olsun. İlkel tabloyu ve iki boyutlu ön-ek sayım tablosunu kurmak \(O(Q^2)\) bellek gerektirir. EBOB testleri ve son eğim sıralaması toplamda \(O(Q^2\log Q+E\log E)\) zaman alır.
Dinamik programlama aşaması yaklaşık
$$O\left(E\sum_{r=1}^{Q-1} H_r\right)$$
adet durum genişletmesi üretir; bunları oluşan listeler üzerinde doğrusal zamanlı zarf birleştirmeleri izler. Son meet-in-the-middle aşamasının maliyeti ise
$$O\left(\sum_{r=1}^{Q-1} H_r H_{Q-r}\right)$$
kadardır. Bu yüzden pratik çalışma süresini, ham poligon sayısından çok filtrelenmiş sınır boyutları belirler. Toplam bellek kullanımı
$$O\left(Q^2+\sum_{r=1}^{Q} H_r\right)$$
şeklindedir.
Sea \(A(N)\) el area minima de un poligono convexo de la reticula con \(N\) lados. Las implementaciones dadas en C++, Python y Java resuelven el caso objetivo \(N\equiv 0 \pmod{4}\) escribiendo \(N=4Q\), construyendo una sola cadena monotona de un cuadrante y recuperando el poligono completo por simetria. Por eso la busqueda no se hace sobre poligonos completos, sino sobre direcciones primitivas ordenadas y resúmenes compactos de su contribucion al area.
La implementacion organiza el poligono como cuatro copias reflejadas de una misma construccion de cuarto de figura. Eso convierte el problema en una optimizacion estructurada sobre direcciones primitivas de la reticula.
Escribimos
$$N=4Q.$$
La estrategia implementada trata un cuarto del poligono optimo como una cadena convexa y monotona. Una media cadena empinada va desde la direccion vertical hasta la diagonal, una media cadena reflejada completa ese cuadrante, y las reflexiones respecto de los ejes coordenados producen los otros tres cuadrantes.
Dentro de la media cadena empinada, cada direccion no trivial de arista se representa mediante un vector primitivo
$$\gcd(x,y)=1,\qquad 1\le x<y.$$
Ordenar estos vectores por su pendiente \(x/y\) impone el orden de giro monotono requerido por la convexidad. Por eso el programa procesa las direcciones en pendiente creciente.
Una cadena de cuadrante tiene exactamente \(Q\) aristas, pero sus dos direcciones extremas ya vienen fijadas por la construccion. Por tanto, solo quedan \(Q-2\) posiciones libres para direcciones primitivas interiores. Para un vector primitivo \((x,y)\), las implementaciones calculan
$$\Pi(x,y)=\#\left\{(u,v):1\le u\le x,\ 1\le v\le y,\ u<v,\ \gcd(u,v)=1\right\}.$$
Eso cuenta cuantas direcciones primitivas hay en el rectangulo suroeste hasta \((x,y)\). Si
$$\Pi(x,y)>Q-2,$$
entonces \((x,y)\) ya aparece demasiado tarde dentro de ese conjunto ordenado como para encajar en una cadena de cuadrante con solo \(Q\) aristas totales, asi que se descarta de inmediato. Esta poda temprana es la razon por la que la lista de candidatos permanece manejable.
Supongamos que las direcciones interiores elegidas hasta el momento en una media cadena empinada son
$$ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k), $$
ya ordenadas por pendiente. Las implementaciones resumen toda esa cadena parcial mediante dos cantidades:
$$\Sigma_k=1+2\sum_{i=1}^{k} y_i,$$
$$\Lambda_k=2\sum_{j=1}^{k} x_j\left(1+y_j+2\sum_{i<j} y_i\right).$$
El estado base es
$$ (\Sigma,\Lambda)=(1,0). $$
Al anadir una nueva direccion primitiva \((x,y)\), el resumen se actualiza mediante
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y).$$
Esta recurrencia es el centro del programa dinamico. Lo importante es que todas las contribuciones futuras de las direcciones ya elegidas quedan codificadas solo en \(\Sigma\) y \(\Lambda\), de modo que no hace falta guardar una descripcion geometrica mas fina.
Para cada longitud posible de cadena, muchos estados alcanzables no sirven. Si dos estados tienen el mismo valor de \(\Sigma\), solo puede ayudar el que tenga menor \(\Lambda\). Las implementaciones van mas alla y conservan unicamente la envolvente convexa inferior de los puntos alcanzables \((\Sigma,\Lambda)\).
La justificacion aparece en la formula final de combinacion. Si la mitad opuesta aporta \((\Sigma_1,\Lambda_1)\), entonces usar un estado \((\Sigma_0,\Lambda_0)\) en el lado actual produce
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2.$$
Para \((\Sigma_1,\Lambda_1)\) fijo, esto puede reescribirse como
$$\mathcal{V}=\bigl(\Lambda_0+(\Sigma_1+2)\Sigma_0\bigr)+C,$$
es decir, un funcional lineal de los puntos del lado izquierdo con pendiente positiva \(\Sigma_1+2\). Por eso, cualquier punto situado por encima de la envolvente convexa inferior nunca puede ser optimo en una combinacion posterior, y el test de producto cruzado elimina exactamente esos estados.
El algoritmo almacena una frontera filtrada para cada numero posible de aristas del cuadrante. Si un lado del cuadrante usa \(\ell\) aristas y el otro usa \(Q-\ell\), cada par de estados de esas dos fronteras produce el area candidata
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2.$$
Se toma el minimo sobre todas las particiones
$$1\le \ell < Q$$
y sobre todos los pares de estados filtrados en las dos fronteras correspondientes. El caso especial \(Q=1\), es decir, \(N=4\), se resuelve directamente y da area \(1\).
Aqui \(Q=2\). Como una cadena de cuadrante solo tiene \(Q-2=0\) posiciones internas, no puede insertarse ninguna direccion primitiva adicional. La unica frontera almacenada en cada lado sigue siendo el estado base
$$ (\Sigma,\Lambda)=(1,0). $$
La unica particion posible es \(1+1\), asi que
$$A(8)=0+0+(1+2)(1+2)-2=9-2=7.$$
Ese valor coincide con el punto de control usado por las implementaciones.
Las implementaciones en C++, Python y Java primero descartan las entradas que no son multiplos de \(4\), y luego fijan \(Q=N/4\). Despues enumeran las direcciones primitivas del primer octante, cuentan cuantas direcciones primitivas menores quedan dentro del rectangulo asociado a cada una y conservan solo las que cumplen el umbral del Paso 2. Las direcciones supervivientes se ordenan por pendiente.
A continuacion, la implementacion mantiene una frontera para cada longitud posible del cuadrante. Partiendo del estado base \((1,0)\), cada direccion candidata se anade a todas las fronteras existentes de menor longitud, lo que genera nuevos estados resumidos mediante
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y).$$
Despues de cada tanda de inserciones, la frontera nueva se fusiona con la ya conocida para esa longitud y se vuelve a filtrar hasta quedarse solo con la envolvente convexa inferior.
Una vez procesadas todas las direcciones, se emparejan las fronteras complementarias de longitudes \(\ell\) y \(Q-\ell\). Para cada par, el programa evalua
$$\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2$$
y conserva el minimo. La implementacion en C++ tambien comprueba varios valores pequenos conocidos antes de calcular el caso objetivo.
Sea \(E\) el numero de direcciones primitivas retenidas tras el corte por rectangulos, y sea \(H_r\) el tamano de la frontera filtrada para la longitud \(r\) del cuadrante. Construir la tabla de primitividad y la tabla bidimensional de prefijos requiere \(O(Q^2)\) memoria. Las pruebas de gcd y la ordenacion final por pendiente aportan \(O(Q^2\log Q+E\log E)\) tiempo.
La fase de programacion dinamica genera aproximadamente
$$O\left(E\sum_{r=1}^{Q-1} H_r\right)$$
extensiones de estado, seguidas de fusiones lineales de envolventes sobre las listas producidas. La etapa final de meet-in-the-middle cuesta
$$O\left(\sum_{r=1}^{Q-1} H_r H_{Q-r}\right).$$
En la practica, el tiempo real depende mucho mas de los tamanos filtrados de frontera que del enorme numero bruto de poligonos convexos de la reticula. El uso total de memoria es
$$O\left(Q^2+\sum_{r=1}^{Q} H_r\right).$$
设 \(A(N)\) 表示具有 \(N\) 条边的凸格点多边形所能取得的最小面积。给出的 C++、Python 和 Java 实现处理的是目标情形 \(N\equiv 0 \pmod{4}\)：先写成 \(N=4Q\)，只构造其中一个象限里的单调链，再通过对称性恢复整个多边形。因此，程序真正搜索的对象不是“所有多边形”，而是按斜率排序的原始边方向，以及这些方向对面积造成影响的压缩状态。
实现采用的是“四个对称象限”模型。这样一来，问题就从直接枚举凸格点多边形，转化成了对原始格点方向进行有结构的优化。
记
$$N=4Q.$$
实现中的策略把最优多边形的一个象限看成一条凸的、单调的边链。其中一半是从竖直方向逐步转向对角线的“陡链”，另一半由它关于对角线的镜像得到；再把整个象限关于坐标轴反射，就得到完整的四个象限。
在这条陡链内部，每一个非平凡边方向都写成一个原始格点向量
$$\gcd(x,y)=1,\qquad 1\le x<y.$$
按斜率 \(x/y\) 从小到大排序之后，方向的出现顺序就符合凸性所要求的单调转向顺序。所以程序始终按这个顺序处理候选边方向。
一个象限链总共有 \(Q\) 条边，但其中两条极端方向已经被构造固定了，因此真正可以自由选择的内部原始方向只有 \(Q-2\) 个。对于一个原始向量 \((x,y)\)，实现会预先计算
$$\Pi(x,y)=\#\left\{(u,v):1\le u\le x,\ 1\le v\le y,\ u<v,\ \gcd(u,v)=1\right\}.$$
这个数表示在 \((x,y)\) 左下方矩形内一共有多少个原始方向。如果已经有
$$\Pi(x,y)>Q-2,$$
那么 \((x,y)\) 在这个有序集合里就已经“排得太靠后”，不可能再塞进一条总长度只有 \(Q\) 的象限链中，所以程序会在动态规划开始前直接把它丢弃。正是这一步预剪枝，让候选方向数量维持在可控范围内。
设某条陡链中当前已经选出的内部方向为
$$ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k), $$
并且已经按斜率排序。实现并不保存整条链的完整几何信息，而是只保存两个汇总量：
$$\Sigma_k=1+2\sum_{i=1}^{k} y_i,$$
$$\Lambda_k=2\sum_{j=1}^{k} x_j\left(1+y_j+2\sum_{i<j} y_i\right).$$
基础状态是
$$ (\Sigma,\Lambda)=(1,0). $$
当在当前部分链末尾再接上一条原始方向 \((x,y)\) 时，状态更新为
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y).$$
这条递推式就是整个动态规划的核心。关键点在于：已经选择过的边在未来会怎样影响总面积，只需要通过 \(\Sigma\) 和 \(\Lambda\) 这两个量传递下去，因此没必要保存更细的局部几何细节。
对于每一种可能的链长，可达状态里有很多都是无用的。如果两个状态具有相同的 \(\Sigma\)，那么只有 \(\Lambda\) 更小的那个才有可能进入最优解。实现进一步保留的其实不是全部状态，而只是可达点 \((\Sigma,\Lambda)\) 的下凸包。
原因可以直接从最后的合并公式看出来。若对侧半链贡献的是 \((\Sigma_1,\Lambda_1)\)，那么当前侧使用 \((\Sigma_0,\Lambda_0)\) 时，总候选值为
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2.$$
对于固定的 \((\Sigma_1,\Lambda_1)\)，上式可以改写成
$$\mathcal{V}=\bigl(\Lambda_0+(\Sigma_1+2)\Sigma_0\bigr)+C,$$
也就是说，它是左侧点集上的一个线性函数，而且斜率 \(\Sigma_1+2\) 恒为正。于是，任何位于下凸包之上的点，都不可能在后续某次合并中成为最优。实现中的叉积判定正是用来删除这些点的。
算法为每一个可能的象限边数都维护一条经过过滤的前沿。如果象限的一侧用了 \(\ell\) 条边，另一侧用了 \(Q-\ell\) 条边，那么这两条前沿中的任意状态对都会产生一个候选面积
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2.$$
程序在所有划分
$$1\le \ell < Q$$
以及对应前沿中的所有状态对上取最小值。特殊情形 \(Q=1\)，也就是 \(N=4\)，直接返回面积 \(1\)。
此时 \(Q=2\)。因为一个象限链只有 \(Q-2=0\) 个内部位置，所以根本没有额外的原始方向可以插入。于是每一侧保存的唯一状态仍然是基础状态
$$ (\Sigma,\Lambda)=(1,0). $$
唯一可行的划分是 \(1+1\)，因此
$$A(8)=0+0+(1+2)(1+2)-2=9-2=7.$$
这与实现中的校验值完全一致。
C++、Python 和 Java 实现首先排除所有不是 \(4\) 的倍数的输入，然后令 \(Q=N/4\)。接着，它们枚举第一八分圆区间中的原始方向，统计每个方向左下矩形中较小原始方向的数量，只保留满足步骤 2 截断条件的候选，并按斜率排序。
之后，程序为每一个可能的象限长度维护一条前沿。它从基础状态 \((1,0)\) 出发，把每个候选方向附加到所有较短前沿里的已有状态上，并用
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y)$$
生成新的压缩状态。每轮扩展之后，新状态都会与同长度的旧前沿合并，再立即过滤回下凸包。
当所有候选都处理完毕后，程序将长度互补的前沿 \(\ell\) 与 \(Q-\ell\) 成对组合。对每一对状态，计算
$$\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2$$
并保留全局最小值。C++ 版本在求目标输入之前，还会先检查若干已知的小规模结果。
设经过矩形截断后保留下来的原始方向数为 \(E\)，设象限长度为 \(r\) 时过滤后的前沿大小为 \(H_r\)。构造原始性表和二维前缀计数表需要 \(O(Q^2)\) 内存。gcd 判定与最终的斜率排序总时间为 \(O(Q^2\log Q+E\log E)\)。
动态规划阶段大约会生成
$$O\left(E\sum_{r=1}^{Q-1} H_r\right)$$
次状态扩展，随后在生成的前沿列表上做线性时间的凸包合并。最后的中途相遇式合并开销为
$$O\left(\sum_{r=1}^{Q-1} H_r H_{Q-r}\right).$$
因此，实际运行时间主要由过滤后前沿的大小决定，而不是由“所有可能的凸格点多边形”这种天文数量决定。总内存占用为
$$O\left(Q^2+\sum_{r=1}^{Q} H_r\right).$$
Пусть \(A(N)\) обозначает минимальную площадь выпуклого решетчатого многоугольника с \(N\) сторонами. Данные реализации на C++, Python и Java работают с целевым случаем \(N\equiv 0 \pmod{4}\): они записывают \(N=4Q\), строят только одну монотонную цепочку для четверти фигуры, а затем восстанавливают весь многоугольник по симметрии. Поэтому поиск ведется не по всем многоугольникам напрямую, а по упорядоченным примитивным направлениям ребер и по компактным сводкам их вклада в площадь.
Реализация рассматривает многоугольник как четыре отраженные копии одной четвертной конструкции. Это переводит задачу в структурированную оптимизацию по примитивным направлениям решетки.
Запишем
$$N=4Q.$$
В используемой схеме одна четверть оптимального многоугольника представляется как выпуклая монотонная цепочка. Одна половина этой цепочки идет от вертикального направления к диагонали, ее зеркальная копия завершает соответствующий квадрант, а отражения относительно координатных осей дают остальные три квадранта.
Внутри крутой половины каждая нетривиальная сторона задается примитивным вектором решетки
$$\gcd(x,y)=1,\qquad 1\le x<y.$$
Сортировка этих векторов по наклону \(x/y\) обеспечивает именно тот порядок поворота, который требуется выпуклости. Поэтому программа всегда обрабатывает направления в порядке возрастания наклона.
У четвертной цепочки ровно \(Q\) ребер, но две крайние направления уже зафиксированы самой конструкцией. Значит, свободно выбирать можно только \(Q-2\) внутренних примитивных направлений. Для примитивного вектора \((x,y)\) реализации заранее вычисляют
$$\Pi(x,y)=\#\left\{(u,v):1\le u\le x,\ 1\le v\le y,\ u<v,\ \gcd(u,v)=1\right\}.$$
Это количество примитивных направлений в юго-западном прямоугольнике до точки \((x,y)\). Если
$$\Pi(x,y)>Q-2,$$
то направление \((x,y)\) находится в этом упорядоченном наборе слишком глубоко и уже не может войти в четвертную цепочку общей длины \(Q\). Поэтому такие направления немедленно отбрасываются. Именно эта ранняя отсечка делает список кандидатов существенно меньше.
Пусть уже выбранные внутренние направления крутой половины равны
$$ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k), $$
и уже расположены по возрастанию наклона. Реализация хранит не всю геометрию цепочки, а только две агрегированные величины:
$$\Sigma_k=1+2\sum_{i=1}^{k} y_i,$$
$$\Lambda_k=2\sum_{j=1}^{k} x_j\left(1+y_j+2\sum_{i<j} y_i\right).$$
Базовое состояние имеет вид
$$ (\Sigma,\Lambda)=(1,0). $$
Если к цепочке добавляется новый примитивный вектор \((x,y)\), то состояние обновляется по правилу
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y).$$
Эта рекуррентная формула составляет ядро динамического программирования. Главный смысл в том, что все будущие вклады уже выбранных ребер зависят только от \(\Sigma\) и \(\Lambda\), так что хранить более детальное описание не требуется.
Для каждой возможной длины цепочки многие достижимые состояния бесполезны. Если у двух состояний одинаковое значение \(\Sigma\), то помочь может только состояние с меньшим \(\Lambda\). Реализации идут дальше и сохраняют только нижнюю выпуклую оболочку множества достижимых точек \((\Sigma,\Lambda)\).
Причина видна из формулы окончательного склеивания. Если противоположная половина дает состояние \((\Sigma_1,\Lambda_1)\), то использование текущего состояния \((\Sigma_0,\Lambda_0)\) приводит к значению
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2.$$
При фиксированных \((\Sigma_1,\Lambda_1)\) это переписывается как
$$\mathcal{V}=\bigl(\Lambda_0+(\Sigma_1+2)\Sigma_0\bigr)+C,$$
то есть как линейный функционал от точек левой стороны с положительным наклоном \(\Sigma_1+2\). Поэтому любая точка выше нижней выпуклой оболочки не может стать оптимальной ни для какого последующего слияния, и именно такие точки удаляет проверка на основе векторного произведения.
Алгоритм хранит по одному отфильтрованному фронту для каждого возможного числа ребер в четверти. Если одна сторона четверти использует \(\ell\) ребер, а другая использует \(Q-\ell\), то каждая пара состояний из этих двух фронтов задает кандидат на площадь:
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2.$$
Минимум берется по всем разбиениям
$$1\le \ell < Q$$
и по всем парам состояний соответствующих фронтов. Частный случай \(Q=1\), то есть \(N=4\), обрабатывается отдельно и дает площадь \(1\).
Здесь \(Q=2\). Так как у четвертной цепочки только \(Q-2=0\) внутренних позиций, ни одно дополнительное примитивное направление вставить нельзя. На каждой стороне остается только базовое состояние
$$ (\Sigma,\Lambda)=(1,0). $$
Единственное возможное разбиение равно \(1+1\), поэтому
$$A(8)=0+0+(1+2)(1+2)-2=9-2=7.$$
Это ровно тот контрольный результат, который используют реализации.
Реализации на C++, Python и Java сначала отбрасывают все входы, не кратные \(4\), затем устанавливают \(Q=N/4\). После этого они перечисляют примитивные направления в первом октанте, подсчитывают для каждого направления число меньших примитивных направлений в соответствующем прямоугольнике и оставляют только те, которые проходят порог из шага 2. Оставшиеся кандидаты сортируются по наклону.
Далее программа поддерживает по одному фронту для каждой возможной четвертной длины. Начиная с базового состояния \((1,0)\), каждое кандидатное направление добавляется ко всем уже существующим фронтам меньшей длины, создавая новые сжатые состояния по правилу
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y).$$
После каждой серии вставок новый фронт сливается со старым фронтом той же длины и сразу же отфильтровывается обратно до нижней выпуклой оболочки.
Когда обработаны все кандидаты, программа соединяет дополнительные фронты длин \(\ell\) и \(Q-\ell\). Для каждой пары вычисляется
$$\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2,$$
после чего сохраняется минимальное значение. Версия на C++ дополнительно проверяет несколько известных малых результатов перед вычислением целевого случая.
Пусть \(E\) — число примитивных направлений, сохранившихся после прямоугольной отсечки, а \(H_r\) — размер отфильтрованного фронта для четвертной длины \(r\). Построение таблицы примитивности и двумерной таблицы префиксных подсчетов требует \(O(Q^2)\) памяти. Проверки gcd и итоговая сортировка по наклону дают суммарно \(O(Q^2\log Q+E\log E)\) времени.
Фаза динамического программирования порождает приблизительно
$$O\left(E\sum_{r=1}^{Q-1} H_r\right)$$
расширений состояний, после чего следуют линейные слияния выпуклых оболочек на полученных списках. Завершающий этап meet in the middle стоит
$$O\left(\sum_{r=1}^{Q-1} H_r H_{Q-r}\right).$$
Тем самым практическое время определяется прежде всего размерами отфильтрованных фронтов, а не гигантским числом всех выпуклых решетчатых многоугольников, которые пришлось бы перебирать напрямую. Полный расход памяти равен
$$O\left(Q^2+\sum_{r=1}^{Q} H_r\right).$$
لتكن \(A(N)\) هي المساحة الدنيا لمضلع شبكي محدب له \(N\) أضلاع. التطبيقات المعطاة بلغة ++C وPython وJava تعالج الحالة المستهدفة \(N\equiv 0 \pmod{4}\) بكتابة \(N=4Q\)، ثم بناء سلسلة رتيبة لربع واحد فقط من المضلع، ثم استعادة المضلع الكامل بالتناظر. لذلك فعملية البحث ليست على جميع المضلعات مباشرة، بل على اتجاهات حواف بدائية مرتبة مع ملخصات مضغوطة لمساهمتها في المساحة.
التنفيذ ينظم المضلع على أنه أربع نسخ منعكسة من بناء ربع واحد. وهذا يحول المسألة إلى تحسين منظم فوق اتجاهات شبكية بدائية.
نكتب
$$N=4Q.$$
في الاستراتيجية المطبقة، يمثل ربع المضلع الأمثل كسلسلة محدبة ورتيبة. نصف السلسلة الحاد يتحرك من الاتجاه الرأسي نحو القطر، ثم يكمل انعكاسه حول القطر ذلك الربع، وبعد ذلك تعطي الانعكاسات حول المحورين الإحداثيين الأرباع الثلاثة الأخرى.
داخل هذا النصف الحاد، يمثل كل اتجاه حافة غير بسيط بمتجه شبكي بدائي
$$\gcd(x,y)=1,\qquad 1\le x<y.$$
وترتيب هذه المتجهات حسب الميل \(x/y\) يفرض ترتيب الدوران الرتيب اللازم للمحدبية. ولهذا تعالج الشفرة الاتجاهات بترتيب الميل المتزايد.
سلسلة الربع تحتوي بالضبط على \(Q\) حواف، لكن اتجاهي الطرفين مثبتان مسبقا بواسطة البناء، ولذلك لا يبقى إلا \(Q-2\) مواضع داخلية لاتجاهات بدائية حرة. لكل متجه بدائي \((x,y)\)، تحسب التطبيقات
$$\Pi(x,y)=\#\left\{(u,v):1\le u\le x,\ 1\le v\le y,\ u<v,\ \gcd(u,v)=1\right\}.$$
وهذا هو عدد الاتجاهات البدائية الواقعة داخل المستطيل الجنوبي الغربي حتى النقطة \((x,y)\). فإذا كان
$$\Pi(x,y)>Q-2,$$
فإن \((x,y)\) يكون متأخرا أكثر من اللازم داخل هذا الترتيب، ولا يمكن أن يدخل في سلسلة ربع طولها الكلي \(Q\) فقط، ولذلك يحذف مباشرة قبل بدء البرمجة الديناميكية. هذا القطع المبكر هو ما يبقي قائمة المرشحين ضمن حجم عملي.
لنفترض أن الاتجاهات الداخلية المختارة حتى الآن في نصف السلسلة الحاد هي
$$ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k), $$
وقد رتبت بالفعل حسب الميل. لا يحتفظ التنفيذ بكل الوصف الهندسي لهذه السلسلة، بل يلخصها في مقدارين:
$$\Sigma_k=1+2\sum_{i=1}^{k} y_i,$$
$$\Lambda_k=2\sum_{j=1}^{k} x_j\left(1+y_j+2\sum_{i<j} y_i\right).$$
الحالة الابتدائية هي
$$ (\Sigma,\Lambda)=(1,0). $$
وعند إلحاق اتجاه بدائي جديد \((x,y)\) تصبح الحالة
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y).$$
هذه العلاقة العودية هي قلب البرمجة الديناميكية. والفكرة الأساسية أن كل الأثر المستقبلي للحواف المختارة سابقا يمر فقط عبر \(\Sigma\) و\(\Lambda\)، ولذلك لا حاجة إلى تخزين تفاصيل هندسية أدق.
لكل طول ممكن للسلسلة توجد حالات كثيرة قابلة للوصول لكنها غير مفيدة. إذا امتلكت حالتان القيمة نفسها لـ \(\Sigma\)، فلا يمكن أن يفيد إلا الأصغر في \(\Lambda\). وتذهب التطبيقات أبعد من ذلك فتحفظ فقط الغلاف المحدب السفلي لنقاط الحالة \((\Sigma,\Lambda)\) القابلة للوصول.
سبب ذلك يظهر من صيغة الدمج النهائية. فإذا ساهم النصف المقابل بالحالة \((\Sigma_1,\Lambda_1)\)، فإن استعمال الحالة \((\Sigma_0,\Lambda_0)\) في هذا الجانب يعطي
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2.$$
وعند تثبيت \((\Sigma_1,\Lambda_1)\) يمكن إعادة كتابة هذا على الصورة
$$\mathcal{V}=\bigl(\Lambda_0+(\Sigma_1+2)\Sigma_0\bigr)+C,$$
أي إنه دالة خطية في نقاط الجانب الأيسر ذات ميل موجب \(\Sigma_1+2\). ومن ثم فإن أي نقطة تقع فوق الغلاف المحدب السفلي لا يمكن أن تكون مثلى في أي دمج لاحق، ولهذا يزيلها اختبار الجداء الاتجاهي المستخدم في التنفيذ.
تخزن الخوارزمية جبهة مفلترة لكل عدد ممكن من حواف الربع. فإذا استعمل أحد جانبي الربع \(\ell\) حواف واستعمل الجانب الآخر \(Q-\ell\) حواف، فإن كل زوج من حالات هاتين الجبهتين يولد مساحة مرشحة
$$\mathcal{V}=\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2.$$
ويؤخذ الحد الأدنى على جميع التقسيمات
$$1\le \ell < Q$$
وعلى جميع أزواج الحالات في الجبهتين الموافقـتين. أما الحالة الخاصة \(Q=1\)، أي \(N=4\)، فتعالج مباشرة وتعطي المساحة \(1\).
هنا \(Q=2\). ولأن سلسلة الربع تملك \(Q-2=0\) مواضع داخلية فقط، فلا يمكن إدخال أي اتجاه بدائي إضافي. ولذلك تبقى الحالة الوحيدة المخزنة على كل جانب هي الحالة الابتدائية
$$ (\Sigma,\Lambda)=(1,0). $$
والتقسيم الوحيد الممكن هو \(1+1\)، ومن ثم
$$A(8)=0+0+(1+2)(1+2)-2=9-2=7.$$
وهذا يطابق تماما قيمة التحقق الموجودة في التطبيقات.
تبدأ تطبيقات ++C وPython وJava برفض أي دخل لا يكون مضاعفا لـ \(4\)، ثم تضبط \(Q=N/4\). بعد ذلك تعدد الاتجاهات البدائية في الثمن الأول، وتحسب لكل اتجاه عدد الاتجاهات البدائية الأصغر الواقعة داخل المستطيل الموافق له، ثم تحتفظ فقط بالاتجاهات التي تحقق شرط القطع المذكور في الخطوة 2. وبعد ذلك ترتب الاتجاهات الباقية حسب الميل.
ثم يحافظ التنفيذ على جبهة واحدة لكل طول ممكن في الربع. انطلاقا من الحالة الأساسية \((1,0)\)، يضاف كل اتجاه مرشح إلى جميع الجبهات الأقصر الموجودة، فتتولد حالات مضغوطة جديدة عبر
$$\Sigma'=\Sigma+2y,\qquad \Lambda'=\Lambda+2x(\Sigma+y).$$
وبعد كل دفعة من الإضافات، تدمج الجبهة الجديدة مع الجبهة القديمة للطول نفسه، ثم تعاد تصفيتها فورا إلى الغلاف المحدب السفلي فقط.
وبعد معالجة كل المرشحين، تزاوج الجبهات المتكاملة ذات الطولين \(\ell\) و\(Q-\ell\). ولكل زوج من الحالات تحسب الشفرة
$$\Lambda_0+\Lambda_1+(\Sigma_0+2)(\Sigma_1+2)-2$$
وتحتفظ بأصغر قيمة. كما أن تنفيذ ++C يفحص عدة قيم صغيرة معروفة قبل حساب الحالة الهدف.
لتكن \(E\) هي عدد الاتجاهات البدائية المحتفظ بها بعد قطع المستطيلات، ولتكن \(H_r\) هي سعة الجبهة المفلترة لطول الربع \(r\). بناء جدول البدائية وجدول العد التراكمي ثنائي البعد يحتاج إلى ذاكرة \(O(Q^2)\). أما اختبارات gcd والترتيب النهائي بحسب الميل فتسهم بزمن كلي مقداره \(O(Q^2\log Q+E\log E)\).
مرحلة البرمجة الديناميكية تولد تقريبا
$$O\left(E\sum_{r=1}^{Q-1} H_r\right)$$
عملية توسيع للحالات، ثم تتبعها عمليات دمج خطية للأغلفة على القوائم المتولدة. أما مرحلة الالتقاء في المنتصف في النهاية فتكلف
$$O\left(\sum_{r=1}^{Q-1} H_r H_{Q-r}\right).$$
وبالتالي فإن زمن التنفيذ العملي تحدده أحجام الجبهات بعد التصفية أكثر بكثير من العدد الفلكي للمضلعات الشبكية المحدبة الممكنة نظريا. والاستهلاك الكلي للذاكرة هو
$$O\left(Q^2+\sum_{r=1}^{Q} H_r\right).$$