Let \(R(a,b)\) denote the number of rectangles that can be placed in an \(a \times b\) cross-hatched grid, where every unit square contains both diagonals. The implementations solve the cumulative quantity
$$S(W,H)=\sum_{a=1}^{\min(W,H)}\sum_{b=1}^{\max(W,H)} R(a,b),$$
so for the target instance we need \(S(47,43)\). The total is symmetric in the two dimensions, so the code immediately normalizes them to \(N=\min(W,H)\) and \(M=\max(W,H)\).
The count naturally splits into two families. Ordinary axis-aligned rectangles admit a direct combinatorial sum. Slanted rectangles, whose sides lie on the diagonal hatch lines, are handled by a 45-degree change of coordinates that turns the geometry into a box-counting problem on an integer lattice.
Everything below is written for \(N \le M\). The crucial point is that the program is not solving a single-grid counting problem in isolation; it is summing rectangle counts over every smaller cross-hatched grid up to the target size.
The cumulative form matters because a rectangle that first appears in a small grid also appears in every larger grid that can contain it. The implementation exploits that viewpoint throughout: once it knows the smallest grid dimensions required by a rectangle, it can count all larger grids containing it in one multiplication instead of re-enumerating the rectangle for every grid size.
An ordinary \(a \times b\) grid contains
$$\binom{a+1}{2}\binom{b+1}{2}$$
axis-aligned rectangles, because we choose two horizontal grid lines and two vertical grid lines. Summing over all admissible sizes gives
$$A(N,M)=\sum_{a=1}^{N}\sum_{b=1}^{M}\binom{a+1}{2}\binom{b+1}{2} =\left(\sum_{a=1}^{N}\binom{a+1}{2}\right)\left(\sum_{b=1}^{M}\binom{b+1}{2}\right) =\binom{N+2}{3}\binom{M+2}{3}.$$
This is exactly the closed form that the implementations add to the answer before doing any geometric work on slanted rectangles.
The slanted rectangles have sides parallel to the two diagonal directions of the hatching. The implementation parameterizes the relevant diagonal-intersection lattice by integers \(0 \le i \le 2N\) and \(0 \le j \le 2M\) with \(i+j\) even, then applies the linear map
$$x=\frac{i+j}{2},\qquad y=\frac{i+2\sigma-j}{2},\qquad \sigma=M+3.$$
The translation by \(\sigma\) only keeps the array indices positive; it does not alter the combinatorics. Under this map, the valid intersection points become the integer lattice points in the diamond-shaped region
$$P_{N,M}=\{(x,y)\in\mathbb{Z}^2: 0\le x+y-\sigma\le 2N,\ 0\le x-y+\sigma\le 2M\}.$$
In these new coordinates, every slanted rectangle in the original cross-hatched grid becomes an ordinary axis-aligned rectangle. That is the central mathematical reduction behind the code.
The implementations mark every point of \(P_{N,M}\) in a padded array and build a 2D prefix sum \(Q\). For a candidate box \(B=[l_x,r_x]\times[l_y,r_y]\), the number of marked lattice points inside is
$$\operatorname{pts}(B)=Q(r_x,r_y)-Q(r_x,l_y-1)-Q(l_x-1,r_y)+Q(l_x-1,l_y-1).$$
If the box lies completely inside the diamond, then every lattice point in the box is valid, so
$$\operatorname{pts}(B)=(r_x-l_x+1)(r_y-l_y+1).$$
This equality is the key invariant tested in the four nested loops. A candidate box contributes exactly when it is completely filled with marked points, which is equivalent to saying that the corresponding slanted rectangle is geometrically valid.
Each valid transformed box corresponds to one slanted rectangle prototype. The implementation converts its extreme transformed coordinates back into the smallest ordinary grid dimensions that can contain it. If \(B=[l_x,r_x]\times[l_y,r_y]\), those minimal dimensions are
$$h_{\min}=\left\lfloor\frac{r_x+r_y-\sigma-1}{2}\right\rfloor,\qquad w_{\min}=\left\lfloor\frac{r_x-l_y+\sigma+1}{2}\right\rfloor.$$
The factor \(1/2\) appears because the transformed lattice measures diagonal half-steps while the grid dimensions are counted in unit squares. Once \(h_{\min}\) and \(w_{\min}\) are known, the same slanted rectangle appears in every cross-hatched grid with height at least \(h_{\min}\) and width at least \(w_{\min}\). Therefore its multiplicity in the cumulative sum is
$$\bigl(N-h_{\min}+1\bigr)\bigl(M-w_{\min}+1\bigr).$$
After normalization, the checkpoint case uses \(N=2\) and \(M=3\). The axis-aligned subtotal is
$$A(2,3)=\binom{4}{3}\binom{5}{3}=40.$$
In the transformed plane, one of the smallest valid boxes corresponds to a slanted rectangle whose minimal container is \(1\times 2\). It is therefore counted in exactly four grid sizes: \(1\times 2\), \(1\times 3\), \(2\times 2\), and \(2\times 3\). That is precisely the multiplicity
$$\bigl(2-1+1\bigr)\bigl(3-2+1\bigr)=4.$$
When all valid boxes are swept, their multiplicities sum to 32. Adding the ordinary rectangles gives
$$40+32=72,$$
which is the checkpoint value used by the C++ and Python implementations.
The C++, Python, and Java implementations first reorder the dimensions so the smaller one comes first. They then add the closed-form axis-aligned subtotal \(\binom{N+2}{3}\binom{M+2}{3}\) immediately.
Next, the implementation allocates a square integer array large enough to hold the translated diamond \(P_{N,M}\). Every admissible parity-matched pair \((i,j)\) is mapped to an integer lattice point, and a 2D prefix sum is computed over that marker array.
The remaining work is an exhaustive scan over all axis-aligned boxes in the transformed plane. For each box, the prefix sum determines in constant time whether the box is fully inside the valid diamond. If it is, the implementation recovers the minimal containing grid dimensions \((h_{\min},w_{\min})\), discards impossible cases, and adds the multiplicity \((N-h_{\min}+1)(M-w_{\min}+1)\) to the running total.
All three languages implement the same mathematics. The C++ and Python versions also expose the small \(3\times 2\) checkpoint, while the Java version directly evaluates the target instance.
The closed-form axis-aligned part is \(O(1)\). Building the transformed marker array and its prefix sums costs \(O(M^2)\) time and \(O(M^2)\) space, because the array side length is \(2M+8\).
The dominant phase is the four-loop sweep over candidate boxes in the transformed plane, which is \(O(M^4)\). For the target instance \(M=47\), this is still easily practical. The overall algorithm is therefore \(O(M^4)\) time and \(O(M^2)\) space after normalization.
Sei \(R(a,b)\) die Anzahl der Rechtecke, die in einem schraffierten \(a \times b\)-Gitter platziert werden können, wobei jedes Einheitsquadrat beide Diagonalen enthält. Die Implementierungen berechnen die kumulative Größe
$$S(W,H)=\sum_{a=1}^{\min(W,H)}\sum_{b=1}^{\max(W,H)} R(a,b),$$
also für den Zielwert \(S(47,43)\). Die Summe ist symmetrisch in beiden Dimensionen, daher wird sofort auf \(N=\min(W,H)\) und \(M=\max(W,H)\) normiert.
Die Zählung zerfällt in zwei Familien. Gewöhnliche achsenparallele Rechtecke besitzen eine direkte kombinatorische Summenformel. Schräge Rechtecke, deren Seiten auf den diagonalen Schraffurlinien liegen, werden mit einer 45-Grad-Koordinatentransformation auf ein Problem des Zählens von Boxen in einem ganzzahligen Gitter reduziert.
Im Folgenden gilt stets \(N \le M\). Der entscheidende Punkt ist, dass das Programm nicht nur Rechtecke in einem einzelnen \(47 \times 43\)-Gitter zählt, sondern die Rechteckzahlen aller kleineren schraffierten Gitter bis zu dieser Zielgröße aufsummiert.
Die kumulative Form ist wichtig, weil ein Rechteck, das erstmals in einem kleinen Gitter möglich ist, auch in jedem größeren Gitter vorkommt, das es enthält. Genau das nutzt die Implementierung aus: Sobald die kleinsten notwendigen Gitterdimensionen eines Rechtecks bekannt sind, kann sein Beitrag zu allen größeren Gittern in einer einzigen Multiplikation erfasst werden.
Ein gewöhnliches \(a \times b\)-Gitter enthält
$$\binom{a+1}{2}\binom{b+1}{2}$$
achsenparallele Rechtecke, denn man wählt zwei horizontale und zwei vertikale Gitterlinien. Summiert man über alle zulässigen Größen, erhält man
$$A(N,M)=\sum_{a=1}^{N}\sum_{b=1}^{M}\binom{a+1}{2}\binom{b+1}{2} =\left(\sum_{a=1}^{N}\binom{a+1}{2}\right)\left(\sum_{b=1}^{M}\binom{b+1}{2}\right) =\binom{N+2}{3}\binom{M+2}{3}.$$
Genau diese geschlossene Formel wird in den Implementierungen vor dem geometrischen Teil zur Antwort addiert.
Die schrägen Rechtecke haben Seiten parallel zu den beiden Diagonalrichtungen der Schraffur. Die Implementierung parametrisiert das relevante Gitter der Diagonalschnittpunkte durch ganze Zahlen \(0 \le i \le 2N\) und \(0 \le j \le 2M\) mit geradem \(i+j\) und verwendet dann die lineare Abbildung
$$x=\frac{i+j}{2},\qquad y=\frac{i+2\sigma-j}{2},\qquad \sigma=M+3.$$
Die Verschiebung um \(\sigma\) sorgt nur für positive Array-Indizes; die Kombinatorik ändert sich dadurch nicht. Unter dieser Abbildung werden die gültigen Schnittpunkte zu den ganzzahligen Punkten in der rautenförmigen Menge
$$P_{N,M}=\{(x,y)\in\mathbb{Z}^2: 0\le x+y-\sigma\le 2N,\ 0\le x-y+\sigma\le 2M\}.$$
In den neuen Koordinaten wird jedes schräge Rechteck des ursprünglichen schraffierten Gitters zu einem gewöhnlichen achsenparallelen Rechteck. Genau das ist die zentrale mathematische Reduktion der Lösung.
Die Implementierungen markieren jeden Punkt von \(P_{N,M}\) in einem gepolsterten Array und berechnen daraus eine 2D-Präfixsumme \(Q\). Für eine Kandidatenbox \(B=[l_x,r_x]\times[l_y,r_y]\) ist die Anzahl der markierten Gitterpunkte im Inneren
$$\operatorname{pts}(B)=Q(r_x,r_y)-Q(r_x,l_y-1)-Q(l_x-1,r_y)+Q(l_x-1,l_y-1).$$
Liegt die Box vollständig innerhalb der Raute, dann ist jeder Gitterpunkt der Box gültig, also
$$\operatorname{pts}(B)=(r_x-l_x+1)(r_y-l_y+1).$$
Diese Gleichheit ist die entscheidende Invariante in den vier geschachtelten Schleifen. Eine Kandidatenbox trägt genau dann bei, wenn sie vollständig mit markierten Punkten gefüllt ist, also vollständig in der gültigen Rautenregion liegt.
Jede gültige transformierte Box entspricht einem Prototyp eines schrägen Rechtecks. Die Implementierung rechnet aus ihren Extremkoordinaten die kleinsten gewöhnlichen Gitterdimensionen aus, die dieses Rechteck enthalten können. Für \(B=[l_x,r_x]\times[l_y,r_y]\) sind diese Minimaldimensionen
$$h_{\min}=\left\lfloor\frac{r_x+r_y-\sigma-1}{2}\right\rfloor,\qquad w_{\min}=\left\lfloor\frac{r_x-l_y+\sigma+1}{2}\right\rfloor.$$
Der Faktor \(1/2\) tritt auf, weil das transformierte Gitter halbe Diagonalschritte misst, die Zielgitter aber in Einheitsquadraten angegeben sind. Sind \(h_{\min}\) und \(w_{\min}\) bekannt, dann erscheint dasselbe schräge Rechteck in jedem schraffierten Gitter mit Höhe mindestens \(h_{\min}\) und Breite mindestens \(w_{\min}\). Seine Multiplizität in der kumulativen Summe ist daher
$$\bigl(N-h_{\min}+1\bigr)\bigl(M-w_{\min}+1\bigr).$$
Nach der Normierung gilt im Prüffall \(N=2\) und \(M=3\). Die achsenparallele Teilsumme ist
$$A(2,3)=\binom{4}{3}\binom{5}{3}=40.$$
In der transformierten Ebene entspricht eine der kleinsten gültigen Boxen einem schrägen Rechteck mit minimalem Behälter \(1\times 2\). Es wird also genau in vier Gittergrößen gezählt: \(1\times 2\), \(1\times 3\), \(2\times 2\) und \(2\times 3\). Das ist genau die Multiplizität
$$\bigl(2-1+1\bigr)\bigl(3-2+1\bigr)=4.$$
Wenn alle gültigen Boxen durchsucht werden, summieren sich ihre Multiplizitäten zu 32. Zusammen mit den gewöhnlichen Rechtecken ergibt das
$$40+32=72,$$
also genau den Prüfwert, den die C++- und Python-Implementierungen verwenden.
Die C++-, Python- und Java-Implementierungen ordnen zuerst die Dimensionen so, dass die kleinere vorne steht. Dann addieren sie sofort die geschlossene achsenparallele Teilsumme \(\binom{N+2}{3}\binom{M+2}{3}\).
Anschließend reserviert die Implementierung ein quadratisches Integer-Array, das groß genug für die verschobene Rautenregion \(P_{N,M}\) ist. Jedes zulässige Paritätspaar \((i,j)\) wird auf einen ganzzahligen Gitterpunkt abgebildet, und über dem Marker-Array wird eine 2D-Präfixsumme berechnet.
Die restliche Arbeit ist ein vollständiger Durchlauf über alle achsenparallelen Boxen der transformierten Ebene. Für jede Box entscheidet die Präfixsumme in konstanter Zeit, ob die Box vollständig in der gültigen Raute liegt. Falls ja, berechnet die Implementierung die minimalen Behälterdimensionen \((h_{\min},w_{\min})\), verwirft unzulässige Fälle und addiert die Multiplizität \((N-h_{\min}+1)(M-w_{\min}+1)\) zur laufenden Summe.
Alle drei Sprachen verwenden dieselbe Mathematik. Die C++- und Python-Versionen stellen zusätzlich den kleinen \(3\times 2\)-Prüfwert bereit, während die Java-Version direkt den Zielwert auswertet.
Der geschlossene achsenparallele Teil ist \(O(1)\). Der Aufbau des transformierten Marker-Arrays samt Präfixsummen kostet \(O(M^2)\) Zeit und \(O(M^2)\) Speicher, weil die Seitenlänge des Arrays \(2M+8\) ist.
Die dominierende Phase ist der Vierfachdurchlauf über alle Kandidatenboxen in der transformierten Ebene, also \(O(M^4)\). Für den Zielwert \(M=47\) ist das weiterhin problemlos praktikabel. Insgesamt ergibt sich damit nach der Normierung eine Laufzeit von \(O(M^4)\) und ein Speicherverbrauch von \(O(M^2)\).
\(R(a,b)\), her birim karenin iki köşegen de içerdiği taralı bir \(a \times b\) ızgaraya yerleştirilebilen dikdörtgen sayısı olsun. Uygulamalar tek bir ızgarayı değil, şu kümülatif toplamı hesaplar:
$$S(W,H)=\sum_{a=1}^{\min(W,H)}\sum_{b=1}^{\max(W,H)} R(a,b).$$
Dolayısıyla hedef nicelik \(S(47,43)\)'tür. Toplam iki boyuta göre simetrik olduğu için kod ilk iş olarak boyutları \(N=\min(W,H)\) ve \(M=\max(W,H)\) olacak şekilde düzenler.
Sayım iki ayrı aileye ayrılır. Eksenlere paralel sıradan dikdörtgenler doğrudan kombinatorik bir formülle toplanır. Kenarları taramanın diyagonal doğruları üzerinde olan eğik dikdörtgenler ise 45 derecelik bir koordinat dönüşümüyle tamsayı kafesi üzerindeki kutu sayma problemine indirgenir.
Aşağıda her yerde \(N \le M\) varsayılır. Temel nokta şu: program yalnızca tek bir \(47 \times 43\) ızgaradaki dikdörtgenleri saymıyor; hedef boyuta kadar olan bütün daha küçük taralı ızgaraların dikdörtgen sayılarını topluyor.
Kümülatif bakış açısı kritiktir; küçük bir ızgarada ortaya çıkan bir dikdörtgen, onu kapsayan her daha büyük ızgarada da vardır. Uygulama tam olarak bundan yararlanır: bir dikdörtgenin sığması için gereken en küçük ızgara boyutları bulunduğunda, onu içeren tüm daha büyük ızgaralara katkısı tek bir çarpımla hesaplanabilir.
Sıradan bir \(a \times b\) ızgara
$$\binom{a+1}{2}\binom{b+1}{2}$$
adet eksen hizalı dikdörtgen içerir; çünkü iki yatay ve iki dikey ızgara doğrusu seçilir. Bunu tüm geçerli boyutlar üzerinden toplarsak
$$A(N,M)=\sum_{a=1}^{N}\sum_{b=1}^{M}\binom{a+1}{2}\binom{b+1}{2} =\left(\sum_{a=1}^{N}\binom{a+1}{2}\right)\left(\sum_{b=1}^{M}\binom{b+1}{2}\right) =\binom{N+2}{3}\binom{M+2}{3}$$
elde edilir. Uygulamaların daha en başta cevaba eklediği kapalı form tam olarak budur.
Eğik dikdörtgenlerin kenarları taramanın iki diyagonal doğrultusuna paraleldir. Uygulama, ilgili diyagonal-kesişim kafesini \(0 \le i \le 2N\) ve \(0 \le j \le 2M\) aralığında, \(i+j\) çift olacak şekilde tamsayılarla parametreleyip şu lineer dönüşümü uygular:
$$x=\frac{i+j}{2},\qquad y=\frac{i+2\sigma-j}{2},\qquad \sigma=M+3.$$
\(\sigma\) kadar kaydırma yalnızca dizi indislerini pozitif tutmak içindir; kombinatoriği değiştirmez. Bu dönüşüm altında geçerli kesişim noktaları şu elmas bölgenin tamsayı noktalarına dönüşür:
$$P_{N,M}=\{(x,y)\in\mathbb{Z}^2: 0\le x+y-\sigma\le 2N,\ 0\le x-y+\sigma\le 2M\}.$$
Yeni koordinatlarda, özgün taralı ızgaradaki her eğik dikdörtgen sıradan bir eksen hizalı dikdörtgene dönüşür. Kodun arkasındaki temel matematiksel indirgeme budur.
Uygulamalar \(P_{N,M}\)'nin her noktasını tamponlu bir diziye işaretler ve bunun üzerinden bir 2B prefix sum \(Q\) kurar. \(B=[l_x,r_x]\times[l_y,r_y]\) aday kutusu için kutunun içindeki işaretli kafes noktası sayısı
$$\operatorname{pts}(B)=Q(r_x,r_y)-Q(r_x,l_y-1)-Q(l_x-1,r_y)+Q(l_x-1,l_y-1)$$
olur. Kutu elmas bölgenin tamamı içindeyse, kutunun her kafes noktası geçerlidir; dolayısıyla
$$\operatorname{pts}(B)=(r_x-l_x+1)(r_y-l_y+1).$$
Dört iç içe döngüde test edilen kilit invariant budur. Bir aday kutu ancak ve ancak tamamen işaretli noktalarla doluysa katkı verir; bu da ilgili eğik dikdörtgenin geometrik olarak geçerli olduğu anlamına gelir.
Her geçerli dönüştürülmüş kutu, eğik bir dikdörtgen prototipine karşılık gelir. Uygulama, kutunun uç koordinatlarından bu dikdörtgeni içerebilen en küçük sıradan ızgara boyutlarını geri hesaplar. \(B=[l_x,r_x]\times[l_y,r_y]\) için bu minimal boyutlar
$$h_{\min}=\left\lfloor\frac{r_x+r_y-\sigma-1}{2}\right\rfloor,\qquad w_{\min}=\left\lfloor\frac{r_x-l_y+\sigma+1}{2}\right\rfloor$$
şeklindedir. \(1/2\) katsayısı, dönüştürülmüş kafesin diyagonal yarım-adımları sayması, hedef ızgara boyutlarının ise birim karelerle ölçülmesinden gelir. \(h_{\min}\) ve \(w_{\min}\) bulunduğunda aynı eğik dikdörtgen, yüksekliği en az \(h_{\min}\) ve genişliği en az \(w_{\min}\) olan her taralı ızgarada bulunur. Bu nedenle kümülatif toplam içindeki çarpanı
$$\bigl(N-h_{\min}+1\bigr)\bigl(M-w_{\min}+1\bigr)$$
olur.
Normalizasyondan sonra kontrol örneğinde \(N=2\) ve \(M=3\) kullanılır. Eksen hizalı ara toplam
$$A(2,3)=\binom{4}{3}\binom{5}{3}=40$$
olur. Dönüştürülmüş düzlemde en küçük geçerli kutulardan biri, minimal kapsayıcısı \(1\times 2\) olan bir eğik dikdörtgene karşılık gelir. Bu nedenle tam olarak şu dört ızgara boyutunda sayılır: \(1\times 2\), \(1\times 3\), \(2\times 2\) ve \(2\times 3\). Bu da tam olarak şu çarpandır:
$$\bigl(2-1+1\bigr)\bigl(3-2+1\bigr)=4.$$
Tüm geçerli kutular tarandığında bu çarpanların toplamı 32 olur. Sıradan dikdörtgenlerle birlikte
$$40+32=72$$
elde edilir; bu, C++ ve Python uygulamalarının kullandığı kontrol değeridir.
C++, Python ve Java uygulamaları ilk olarak boyutları yeniden sıralayıp küçük olanı öne alır. Ardından kapalı formdaki eksen hizalı ara toplam \(\binom{N+2}{3}\binom{M+2}{3}\) doğrudan cevaba eklenir.
Sonraki adımda uygulama, ötelenmiş elmas bölge \(P_{N,M}\)'yi tutacak kadar büyük kare bir tamsayı dizisi ayırır. Paritesi uygun her \((i,j)\) çifti bir tamsayı kafes noktasına eşlenir ve işaret dizisinin üzerinden 2B prefix sum hesaplanır.
Kalan iş, dönüştürülmüş düzlemdeki bütün eksen hizalı kutular üzerinde tam bir taramadır. Her kutu için prefix sum, kutunun geçerli elmas bölgenin tamamı içinde olup olmadığını sabit zamanda belirler. Geçerliyse uygulama minimal kapsayıcı ızgara boyutlarını \((h_{\min},w_{\min})\) geri hesaplar, imkânsız durumları atar ve \((N-h_{\min}+1)(M-w_{\min}+1)\) katkısını çalışan toplama ekler.
Üç dilin tamamı aynı matematiği uygular. C++ ve Python sürümleri ek olarak küçük \(3\times 2\) kontrolünü de sunar; Java sürümü ise doğrudan hedef durumu hesaplar.
Kapalı formdaki eksen hizalı kısım \(O(1)\)'dir. Dönüştürülmüş işaret dizisini ve prefix sum tablosunu kurmak, dizi kenarı \(2M+8\) olduğu için \(O(M^2)\) zaman ve \(O(M^2)\) bellek gerektirir.
Baskın faz, dönüştürülmüş düzlemdeki tüm aday kutular üzerindeki dörtlü taramadır; bu da \(O(M^4)\)'tür. Hedef durum için \(M=47\) olduğundan bu maliyet rahatlıkla uygulanabilir seviyededir. Sonuç olarak algoritma normalizasyondan sonra \(O(M^4)\) zamanda ve \(O(M^2)\) bellekte çalışır.
Sea \(R(a,b)\) el número de rectángulos que pueden colocarse en una cuadrícula rayada de \(a \times b\), donde cada cuadrado unitario contiene ambas diagonales. Las implementaciones calculan la cantidad acumulada
$$S(W,H)=\sum_{a=1}^{\min(W,H)}\sum_{b=1}^{\max(W,H)} R(a,b),$$
de modo que para el caso objetivo necesitamos \(S(47,43)\). Como la expresión es simétrica en las dos dimensiones, el código las normaliza inmediatamente a \(N=\min(W,H)\) y \(M=\max(W,H)\).
El recuento se divide de forma natural en dos familias. Los rectángulos ordinarios alineados con los ejes tienen una suma combinatoria directa. Los rectángulos inclinados, cuyas aristas siguen las diagonales del tramado, se manejan con un cambio de coordenadas de 45 grados que convierte la geometría en un problema de contar cajas sobre una red entera.
En todo lo que sigue se supone \(N \le M\). El punto clave es que el programa no resuelve solo el conteo en una única cuadrícula \(47 \times 43\); suma los números de rectángulos de todas las cuadrículas rayadas más pequeñas hasta ese tamaño.
La forma acumulada es importante porque un rectángulo que aparece por primera vez en una cuadrícula pequeña también aparece en toda cuadrícula mayor que pueda contenerlo. La implementación explota exactamente esa idea: una vez conocidas las dimensiones mínimas de la cuadrícula que necesita un rectángulo, su contribución a todas las cuadrículas mayores se obtiene con una sola multiplicación.
Una cuadrícula ordinaria de \(a \times b\) contiene
$$\binom{a+1}{2}\binom{b+1}{2}$$
rectángulos alineados con los ejes, porque basta elegir dos líneas horizontales y dos verticales. Al sumar sobre todos los tamaños admisibles se obtiene
$$A(N,M)=\sum_{a=1}^{N}\sum_{b=1}^{M}\binom{a+1}{2}\binom{b+1}{2} =\left(\sum_{a=1}^{N}\binom{a+1}{2}\right)\left(\sum_{b=1}^{M}\binom{b+1}{2}\right) =\binom{N+2}{3}\binom{M+2}{3}.$$
Esta es exactamente la forma cerrada que las implementaciones añaden a la respuesta antes de tratar los rectángulos inclinados.
Los rectángulos inclinados tienen lados paralelos a las dos direcciones diagonales del rayado. La implementación parametriza la red relevante de intersecciones diagonales mediante enteros \(0 \le i \le 2N\) y \(0 \le j \le 2M\) con \(i+j\) par, y luego aplica la transformación lineal
$$x=\frac{i+j}{2},\qquad y=\frac{i+2\sigma-j}{2},\qquad \sigma=M+3.$$
La traslación por \(\sigma\) solo sirve para mantener positivos los índices del arreglo; no altera la combinatoria. Bajo esta transformación, los puntos de intersección válidos pasan a ser los puntos enteros de la región en forma de rombo
$$P_{N,M}=\{(x,y)\in\mathbb{Z}^2: 0\le x+y-\sigma\le 2N,\ 0\le x-y+\sigma\le 2M\}.$$
En las nuevas coordenadas, todo rectángulo inclinado de la cuadrícula rayada original se convierte en un rectángulo ordinario alineado con los ejes. Esa es la reducción matemática central del método.
Las implementaciones marcan cada punto de \(P_{N,M}\) en un arreglo con borde extra y construyen una suma prefija bidimensional \(Q\). Para una caja candidata \(B=[l_x,r_x]\times[l_y,r_y]\), el número de puntos marcados en su interior es
$$\operatorname{pts}(B)=Q(r_x,r_y)-Q(r_x,l_y-1)-Q(l_x-1,r_y)+Q(l_x-1,l_y-1).$$
Si la caja está completamente dentro del rombo, entonces cada punto de la red en la caja es válido, y por tanto
$$\operatorname{pts}(B)=(r_x-l_x+1)(r_y-l_y+1).$$
Esa igualdad es el invariante clave comprobado dentro de los cuatro bucles anidados. Una caja candidata aporta exactamente cuando está totalmente llena de puntos marcados, lo que equivale a que el rectángulo inclinado correspondiente sea geométricamente posible.
Cada caja válida en las coordenadas transformadas corresponde a un prototipo de rectángulo inclinado. La implementación convierte sus coordenadas extremas de nuevo en las dimensiones mínimas de la cuadrícula ordinaria que puede contenerlo. Si \(B=[l_x,r_x]\times[l_y,r_y]\), esas dimensiones mínimas son
$$h_{\min}=\left\lfloor\frac{r_x+r_y-\sigma-1}{2}\right\rfloor,\qquad w_{\min}=\left\lfloor\frac{r_x-l_y+\sigma+1}{2}\right\rfloor.$$
El factor \(1/2\) aparece porque la red transformada mide medios pasos diagonales, mientras que las dimensiones de la cuadrícula se miden en cuadrados unitarios. Una vez conocidos \(h_{\min}\) y \(w_{\min}\), el mismo rectángulo inclinado aparece en toda cuadrícula rayada cuya altura sea al menos \(h_{\min}\) y cuya anchura sea al menos \(w_{\min}\). Por eso su multiplicidad en la suma acumulada es
$$\bigl(N-h_{\min}+1\bigr)\bigl(M-w_{\min}+1\bigr).$$
Tras la normalización, el caso de comprobación usa \(N=2\) y \(M=3\). El subtotal alineado con los ejes es
$$A(2,3)=\binom{4}{3}\binom{5}{3}=40.$$
En el plano transformado, una de las cajas válidas más pequeñas corresponde a un rectángulo inclinado cuyo contenedor mínimo es \(1\times 2\). Por ello se cuenta exactamente en cuatro tamaños de cuadrícula: \(1\times 2\), \(1\times 3\), \(2\times 2\) y \(2\times 3\). Esa es precisamente la multiplicidad
$$\bigl(2-1+1\bigr)\bigl(3-2+1\bigr)=4.$$
Al recorrer todas las cajas válidas, la suma de sus multiplicidades es 32. Al añadir los rectángulos ordinarios se obtiene
$$40+32=72,$$
que es el valor de comprobación usado por las implementaciones en C++ y Python.
Las implementaciones en C++, Python y Java reordenan primero las dimensiones para que la menor vaya delante. Luego añaden inmediatamente el subtotal cerrado de rectángulos alineados con los ejes, \(\binom{N+2}{3}\binom{M+2}{3}\).
Después, la implementación reserva un arreglo cuadrado de enteros lo bastante grande para contener el rombo trasladado \(P_{N,M}\). Cada par admisible \((i,j)\) con la paridad correcta se transforma en un punto entero de la red, y sobre ese arreglo de marcas se calcula una suma prefija bidimensional.
El trabajo restante es un barrido exhaustivo de todas las cajas alineadas con los ejes en el plano transformado. Para cada caja, la suma prefija decide en tiempo constante si la caja está completamente dentro del rombo válido. Si lo está, la implementación recupera las dimensiones mínimas del contenedor \((h_{\min},w_{\min})\), descarta los casos imposibles y suma la multiplicidad \((N-h_{\min}+1)(M-w_{\min}+1)\) al total acumulado.
Los tres lenguajes implementan exactamente la misma matemática. Las versiones de C++ y Python también exponen la pequeña comprobación \(3\times 2\), mientras que la versión Java evalúa directamente la instancia objetivo.
La parte cerrada de rectángulos alineados con los ejes es \(O(1)\). Construir el arreglo de marcas transformado y sus sumas prefijas cuesta \(O(M^2)\) tiempo y \(O(M^2)\) memoria, porque el lado del arreglo es \(2M+8\).
La fase dominante es el barrido con cuatro bucles sobre las cajas candidatas del plano transformado, que cuesta \(O(M^4)\). Para la instancia real \(M=47\), sigue siendo totalmente práctico. En conjunto, tras la normalización, el algoritmo trabaja en \(O(M^4)\) tiempo y \(O(M^2)\) espacio.
设 \(R(a,b)\) 表示在一个 \(a \times b\) 的交叉阴影网格中可以放置的矩形数量，其中每个单位方格都画出了两条对角线。实现代码求的不是单个网格的值，而是累计量
$$S(W,H)=\sum_{a=1}^{\min(W,H)}\sum_{b=1}^{\max(W,H)} R(a,b).$$
因此目标实例是 \(S(47,43)\)。由于这个总和对两个维度是对称的，代码会先把尺寸规范化为 \(N=\min(W,H)\) 和 \(M=\max(W,H)\)。
整个计数自然分成两类。普通的轴对齐矩形可以直接用组合公式求和。沿着斜线方向的倾斜矩形则通过一个 45 度坐标变换转化为整数点阵上的盒子计数问题。
下面统一假设 \(N \le M\)。关键在于：程序并不是只计算单个 \(47 \times 43\) 网格中的矩形数，而是把所有不超过该尺寸的交叉阴影网格的矩形数全部累加起来。
累计视角非常重要，因为一个在较小网格中首次出现的矩形，也会出现在所有能够容纳它的更大网格中。实现代码正是利用了这一点：一旦知道某个矩形所需的最小网格尺寸，就可以用一次乘法算出它对所有更大网格的总贡献，而不必对每个尺寸重新枚举。
普通的 \(a \times b\) 网格中，轴对齐矩形的个数是
$$\binom{a+1}{2}\binom{b+1}{2}$$
因为只需要选择两条水平网格线和两条垂直网格线。把所有允许的尺寸都加起来，可得
$$A(N,M)=\sum_{a=1}^{N}\sum_{b=1}^{M}\binom{a+1}{2}\binom{b+1}{2} =\left(\sum_{a=1}^{N}\binom{a+1}{2}\right)\left(\sum_{b=1}^{M}\binom{b+1}{2}\right) =\binom{N+2}{3}\binom{M+2}{3}.$$
这正是实现一开始直接加入答案的闭式部分。
倾斜矩形的边平行于阴影中的两组对角线方向。实现代码用整数 \(0 \le i \le 2N\)、\(0 \le j \le 2M\) 且 \(i+j\) 为偶数来参数化相关的对角线交点格，然后施加线性变换
$$x=\frac{i+j}{2},\qquad y=\frac{i+2\sigma-j}{2},\qquad \sigma=M+3.$$
其中 \(\sigma\) 只是为了把数组下标整体平移到正区间，并不改变组合结构。经过这个变换，所有合法交点恰好变成菱形区域中的整数点：
$$P_{N,M}=\{(x,y)\in\mathbb{Z}^2: 0\le x+y-\sigma\le 2N,\ 0\le x-y+\sigma\le 2M\}.$$
在新坐标系中，原交叉阴影网格中的每个倾斜矩形都会变成一个普通的轴对齐矩形。这就是整个程序最核心的数学化简。
实现代码把 \(P_{N,M}\) 的每个点都标记到一个带边界缓冲的数组里，并据此构造二维前缀和 \(Q\)。对候选盒子 \(B=[l_x,r_x]\times[l_y,r_y]\)，其中被标记的格点数为
$$\operatorname{pts}(B)=Q(r_x,r_y)-Q(r_x,l_y-1)-Q(l_x-1,r_y)+Q(l_x-1,l_y-1).$$
如果这个盒子完全位于菱形区域内部，那么盒子中的每个整数格点都必须是合法点，因此有
$$\operatorname{pts}(B)=(r_x-l_x+1)(r_y-l_y+1).$$
这就是四重循环中检查的关键不变量。只有当候选盒子被合法点完全填满时，它才对应一个真正可行的倾斜矩形。
每个有效的变换后盒子都对应一个倾斜矩形原型。实现代码会把它的极值坐标重新换算成能够容纳它的最小普通网格尺寸。若 \(B=[l_x,r_x]\times[l_y,r_y]\)，那么这两个最小尺寸是
$$h_{\min}=\left\lfloor\frac{r_x+r_y-\sigma-1}{2}\right\rfloor,\qquad w_{\min}=\left\lfloor\frac{r_x-l_y+\sigma+1}{2}\right\rfloor.$$
这里出现 \(1/2\)，是因为变换后的格点系统按对角线的半步计数，而原问题的网格尺寸按单位方格计数。得到 \(h_{\min}\) 和 \(w_{\min}\) 后，同一个倾斜矩形就会出现在所有高度至少为 \(h_{\min}\)、宽度至少为 \(w_{\min}\) 的交叉阴影网格中，因此它在累计总和中的重数为
$$\bigl(N-h_{\min}+1\bigr)\bigl(M-w_{\min}+1\bigr).$$
规范化之后，检查例子使用的是 \(N=2\)、\(M=3\)。轴对齐部分的子总和为
$$A(2,3)=\binom{4}{3}\binom{5}{3}=40.$$
在变换后的平面里，最小的有效盒子之一对应一个最小容器为 \(1\times 2\) 的倾斜矩形。因此它会恰好出现在四种网格尺寸中：\(1\times 2\)、\(1\times 3\)、\(2\times 2\) 和 \(2\times 3\)。这正好就是重数
$$\bigl(2-1+1\bigr)\bigl(3-2+1\bigr)=4.$$
当实现把所有有效盒子都扫过之后，它们的重数之和是 32。再加上普通矩形得到
$$40+32=72,$$
这正是 C++ 和 Python 实现中使用的检查值。
C++、Python 和 Java 三个实现都会先把两个尺寸重新排序，使较小者在前。然后立刻把轴对齐矩形的闭式总和 \(\binom{N+2}{3}\binom{M+2}{3}\) 加入答案。
接着，实现会分配一个足够大的方形整数数组，用来容纳平移后的菱形区域 \(P_{N,M}\)。每个满足奇偶条件的 \((i,j)\) 都会被映射成一个整数格点，然后在这个标记数组上计算二维前缀和。
剩下的工作是在变换平面中穷举所有轴对齐盒子。对每个盒子，前缀和都能在常数时间内判断它是否完全落在合法菱形内部。如果是，就恢复对应的最小容器尺寸 \((h_{\min},w_{\min})\)，排除不可能情况，并把 \((N-h_{\min}+1)(M-w_{\min}+1)\) 加到运行总和里。
三种语言实现的是同一套数学。C++ 和 Python 还保留了小型 \(3\times 2\) 检查，而 Java 版本则直接求目标实例。
轴对齐矩形的闭式部分是 \(O(1)\)。构造变换后的标记数组及其前缀和需要 \(O(M^2)\) 时间和 \(O(M^2)\) 空间，因为数组边长是 \(2M+8\)。
主导步骤是对变换平面中所有候选盒子的四重扫描，时间复杂度为 \(O(M^4)\)。对于目标实例 \(M=47\)，这个规模仍然完全可行。因此，归一化之后的整体复杂度是 \(O(M^4)\) 时间和 \(O(M^2)\) 空间。
Пусть \(R(a,b)\) обозначает число прямоугольников, которые можно разместить в заштрихованной сетке размера \(a \times b\), где в каждом единичном квадрате проведены обе диагонали. Реализации вычисляют не только значение для одной сетки, а накопленную величину
$$S(W,H)=\sum_{a=1}^{\min(W,H)}\sum_{b=1}^{\max(W,H)} R(a,b).$$
Значит, для целевого случая нужно найти \(S(47,43)\). Поскольку выражение симметрично по двум размерам, код сразу нормализует их до \(N=\min(W,H)\) и \(M=\max(W,H)\).
Подсчёт естественно распадается на две части. Обычные прямоугольники, параллельные осям, считаются по прямой комбинаторной формуле. Наклонные прямоугольники, чьи стороны идут вдоль диагональных штрихов, обрабатываются через замену координат на 45 градусов, которая превращает геометрию в задачу о подсчёте прямоугольных блоков на целочисленной решётке.
Ниже предполагается \(N \le M\). Существенно, что программа не решает задачу только для одной сетки \(47 \times 43\); она суммирует количество прямоугольников по всем меньшим заштрихованным сеткам вплоть до этого размера.
Накопленная форма важна потому, что прямоугольник, который впервые появляется в маленькой сетке, присутствует и во всякой большей сетке, способной его вместить. Реализация использует именно эту идею: как только известны минимальные размеры сетки, необходимые для данного прямоугольника, вклад во все большие сетки вычисляется одной формулой, без повторного перебора для каждого размера.
Обычная сетка \(a \times b\) содержит
$$\binom{a+1}{2}\binom{b+1}{2}$$
осевых прямоугольников, потому что нужно выбрать две горизонтальные и две вертикальные линии сетки. Суммируя по всем допустимым размерам, получаем
$$A(N,M)=\sum_{a=1}^{N}\sum_{b=1}^{M}\binom{a+1}{2}\binom{b+1}{2} =\left(\sum_{a=1}^{N}\binom{a+1}{2}\right)\left(\sum_{b=1}^{M}\binom{b+1}{2}\right) =\binom{N+2}{3}\binom{M+2}{3}.$$
Именно эта замкнутая формула добавляется к ответу до начала геометрической части, связанной с наклонными прямоугольниками.
Стороны наклонных прямоугольников параллельны двум диагональным направлениям штриховки. Реализация параметризует соответствующую решётку диагональных пересечений целыми числами \(0 \le i \le 2N\) и \(0 \le j \le 2M\) при чётном \(i+j\), а затем применяет линейное преобразование
$$x=\frac{i+j}{2},\qquad y=\frac{i+2\sigma-j}{2},\qquad \sigma=M+3.$$
Сдвиг на \(\sigma\) нужен только для положительных индексов массива и не меняет комбинаторику. После преобразования допустимые точки пересечения становятся целыми точками ромбовидной области
$$P_{N,M}=\{(x,y)\in\mathbb{Z}^2: 0\le x+y-\sigma\le 2N,\ 0\le x-y+\sigma\le 2M\}.$$
В новых координатах каждый наклонный прямоугольник исходной заштрихованной сетки превращается в обычный прямоугольник, параллельный осям. Это и есть главное математическое упрощение метода.
Реализации отмечают каждую точку множества \(P_{N,M}\) в массиве с дополнительной рамкой и строят по нему двумерную префиксную сумму \(Q\). Для кандидата \(B=[l_x,r_x]\times[l_y,r_y]\) число отмеченных точек внутри равно
$$\operatorname{pts}(B)=Q(r_x,r_y)-Q(r_x,l_y-1)-Q(l_x-1,r_y)+Q(l_x-1,l_y-1).$$
Если блок целиком лежит внутри ромба, то каждая целая точка блока допустима, и поэтому
$$\operatorname{pts}(B)=(r_x-l_x+1)(r_y-l_y+1).$$
Именно это равенство является ключевым инвариантом в четырёх вложенных циклах. Кандидат учитывается тогда и только тогда, когда он полностью заполнен допустимыми точками, то есть соответствует реально существующему наклонному прямоугольнику.
Каждый допустимый блок в преобразованных координатах соответствует одному прототипу наклонного прямоугольника. Реализация переводит его крайние координаты обратно в минимальные размеры обычной сетки, которая может его содержать. Для \(B=[l_x,r_x]\times[l_y,r_y]\) эти размеры равны
$$h_{\min}=\left\lfloor\frac{r_x+r_y-\sigma-1}{2}\right\rfloor,\qquad w_{\min}=\left\lfloor\frac{r_x-l_y+\sigma+1}{2}\right\rfloor.$$
Коэффициент \(1/2\) возникает потому, что преобразованная решётка измеряет полу-шаги вдоль диагоналей, а размеры исходных сеток считаются в единичных квадратах. Когда найдены \(h_{\min}\) и \(w_{\min}\), тот же наклонный прямоугольник присутствует во всякой заштрихованной сетке высоты не меньше \(h_{\min}\) и ширины не меньше \(w_{\min}\). Значит, его кратность в накопленной сумме равна
$$\bigl(N-h_{\min}+1\bigr)\bigl(M-w_{\min}+1\bigr).$$
После нормализации в контрольном случае получаем \(N=2\) и \(M=3\). Подсумма для осевых прямоугольников равна
$$A(2,3)=\binom{4}{3}\binom{5}{3}=40.$$
В преобразованной плоскости один из самых маленьких допустимых блоков соответствует наклонному прямоугольнику с минимальным контейнером \(1\times 2\). Поэтому он учитывается ровно в четырёх размерах сетки: \(1\times 2\), \(1\times 3\), \(2\times 2\) и \(2\times 3\). Это как раз множитель
$$\bigl(2-1+1\bigr)\bigl(3-2+1\bigr)=4.$$
При полном переборе всех допустимых блоков сумма их кратностей даёт 32. Вместе с обычными прямоугольниками получаем
$$40+32=72,$$
что и служит контрольным значением в реализациях на C++ и Python.
Реализации на C++, Python и Java сначала переставляют размеры так, чтобы меньший стоял первым. Затем они сразу добавляют к ответу замкнутую сумму для осевых прямоугольников \(\binom{N+2}{3}\binom{M+2}{3}\).
Далее реализация выделяет квадратный целочисленный массив, достаточно большой для сдвинутой ромбовидной области \(P_{N,M}\). Каждая допустимая пара \((i,j)\) правильной чётности отображается в целую точку решётки, после чего по массиву меток строится двумерная префиксная сумма.
Оставшаяся работа представляет собой полный перебор всех осевых блоков в преобразованной плоскости. Для каждого блока префиксная сумма за постоянное время определяет, целиком ли он лежит внутри допустимого ромба. Если да, реализация восстанавливает минимальные размеры контейнера \((h_{\min},w_{\min})\), отбрасывает невозможные случаи и добавляет к текущей сумме множитель \((N-h_{\min}+1)(M-w_{\min}+1)\).
Во всех трёх языках используется одна и та же математика. Версии C++ и Python дополнительно содержат маленькую проверку \(3\times 2\), тогда как Java-версия сразу вычисляет целевой случай.
Замкнутая часть для осевых прямоугольников имеет сложность \(O(1)\). Построение преобразованного массива меток и его префиксных сумм требует \(O(M^2)\) времени и \(O(M^2)\) памяти, потому что сторона массива равна \(2M+8\).
Доминирующая стадия - это четыре вложенных цикла по всем кандидатным блокам в преобразованной плоскости, то есть \(O(M^4)\). Для целевого случая \(M=47\) это по-прежнему вполне практично. Итак, после нормализации общий алгоритм работает за \(O(M^4)\) времени и использует \(O(M^2)\) памяти.
لتكن \(R(a,b)\) عدد المستطيلات التي يمكن وضعها داخل شبكة مظللة متقاطعة من الحجم \(a \times b\)، حيث يحتوي كل مربع وحدوي على القطرين معًا. ما تحسبه التطبيقات ليس قيمة شبكة واحدة فقط، بل المقدار التراكمي
$$S(W,H)=\sum_{a=1}^{\min(W,H)}\sum_{b=1}^{\max(W,H)} R(a,b).$$
لذلك فالحالة المطلوبة هي \(S(47,43)\). وبما أن المجموع متماثل في البعدين، فإن الكود يعيد ترتيب الأبعاد مباشرة إلى \(N=\min(W,H)\) و \(M=\max(W,H)\).
ينقسم العد طبيعيًا إلى عائلتين. المستطيلات العادية المحاذية للمحور تُحسب بصيغة توافقية مباشرة. أما المستطيلات المائلة التي تسير أضلاعها على خطوط التهشير القطرية فتُعالج عبر تحويل إحداثيات بزاوية 45 درجة يحول المسألة إلى عد صناديق على شبكة نقاط صحيحة.
فيما يلي نفترض دائمًا أن \(N \le M\). النقطة الجوهرية أن البرنامج لا يحل مسألة شبكة \(47 \times 43\) منفردة، بل يجمع أعداد المستطيلات لكل الشبكات المظللة الأصغر حتى هذا المقاس.
الصيغة التراكمية مهمة لأن أي مستطيل يظهر أولًا في شبكة صغيرة سيظهر أيضًا في كل شبكة أكبر تستطيع احتواءه. تستفيد التطبيقات من هذه الفكرة مباشرة: ما إن تُعرف أصغر أبعاد شبكة يحتاجها مستطيل معيّن، حتى يمكن حساب مساهمته في جميع الشبكات الأكبر بضربة واحدة بدل إعادة تعداد ذلك المستطيل لكل مقاس على حدة.
تحتوي شبكة عادية من الحجم \(a \times b\) على
$$\binom{a+1}{2}\binom{b+1}{2}$$
مستطيلًا محاذيًا للمحور، لأننا نختار خطين أفقيين وخطين رأسيين من خطوط الشبكة. وبجمع ذلك على جميع المقاسات المسموح بها نحصل على
$$A(N,M)=\sum_{a=1}^{N}\sum_{b=1}^{M}\binom{a+1}{2}\binom{b+1}{2} =\left(\sum_{a=1}^{N}\binom{a+1}{2}\right)\left(\sum_{b=1}^{M}\binom{b+1}{2}\right) =\binom{N+2}{3}\binom{M+2}{3}.$$
وهذه هي الصيغة المغلقة التي تضيفها التطبيقات إلى الجواب قبل البدء بالجزء الهندسي الخاص بالمستطيلات المائلة.
أضلاع المستطيلات المائلة تكون موازية للاتجاهين القطريين في التهشير. تقوم التطبيقات بترميز شبكة تقاطعات الأقطار ذات الصلة بواسطة عددين صحيحين \(0 \le i \le 2N\) و \(0 \le j \le 2M\) مع شرط أن يكون \(i+j\) زوجيًا، ثم تطبق التحويل الخطي
$$x=\frac{i+j}{2},\qquad y=\frac{i+2\sigma-j}{2},\qquad \sigma=M+3.$$
الإزاحة بمقدار \(\sigma\) هدفها فقط إبقاء فهارس المصفوفة موجبة، ولا تغيّر البنية التوافقية. بعد هذا التحويل تصبح نقاط التقاطع الصالحة هي النقاط الصحيحة داخل المنطقة الماسية
$$P_{N,M}=\{(x,y)\in\mathbb{Z}^2: 0\le x+y-\sigma\le 2N,\ 0\le x-y+\sigma\le 2M\}.$$
في هذه الإحداثيات الجديدة يتحول كل مستطيل مائل في الشبكة الأصلية إلى مستطيل عادي محاذٍ للمحور. وهذا هو الاختزال الرياضي المركزي الذي تعتمد عليه الحلول.
تضع التطبيقات علامة على كل نقطة من \(P_{N,M}\) داخل مصفوفة ذات حافة إضافية، ثم تبني مجموع بادئات ثنائي الأبعاد \(Q\). وإذا أخذنا صندوقًا مرشحًا \(B=[l_x,r_x]\times[l_y,r_y]\)، فإن عدد النقاط المعلّمة بداخله هو
$$\operatorname{pts}(B)=Q(r_x,r_y)-Q(r_x,l_y-1)-Q(l_x-1,r_y)+Q(l_x-1,l_y-1).$$
إذا كان الصندوق بكامله داخل المنطقة الماسية، فكل نقطة صحيحة بداخله يجب أن تكون صالحة، ومن ثم
$$\operatorname{pts}(B)=(r_x-l_x+1)(r_y-l_y+1).$$
هذه المساواة هي الثابت الأساسي الذي تفحصه الحلقات الأربع المتداخلة. لا يساهم الصندوق المرشح إلا إذا كان ممتلئًا بالكامل بنقاط معلّمة، وهذا يكافئ أن المستطيل المائل المقابل له صالح هندسيًا.
كل صندوق صالح في الإحداثيات المحولة يقابل نموذجًا واحدًا لمستطيل مائل. وتحوّل التطبيقات إحداثياته القصوى مرة أخرى إلى أصغر أبعاد شبكة عادية يمكن أن تحتويه. فإذا كان \(B=[l_x,r_x]\times[l_y,r_y]\)، فإن هذين البعدين الأدنى يساويان
$$h_{\min}=\left\lfloor\frac{r_x+r_y-\sigma-1}{2}\right\rfloor,\qquad w_{\min}=\left\lfloor\frac{r_x-l_y+\sigma+1}{2}\right\rfloor.$$
يظهر العامل \(1/2\) لأن الشبكة المحولة تقيس أنصاف الخطوات القطرية، بينما تقاس أبعاد الشبكات الأصلية بعدد المربعات الوحدوية. وبمجرد معرفة \(h_{\min}\) و \(w_{\min}\)، فإن المستطيل المائل نفسه يظهر في كل شبكة مظللة ارتفاعها على الأقل \(h_{\min}\) وعرضها على الأقل \(w_{\min}\). لذلك تكون مضاعفيته في المجموع التراكمي
$$\bigl(N-h_{\min}+1\bigr)\bigl(M-w_{\min}+1\bigr).$$
بعد التطبيع يصبح لدينا في مثال الفحص \(N=2\) و \(M=3\). ويكون المجموع الجزئي للمستطيلات المحاذية للمحور
$$A(2,3)=\binom{4}{3}\binom{5}{3}=40.$$
في المستوى المحول، أحد أصغر الصناديق الصالحة يقابل مستطيلًا مائلًا يحتاج إلى حاوية دنيا \(1\times 2\). ولذلك يُحسب هذا المستطيل في أربعة مقاسات فقط: \(1\times 2\)، \(1\times 3\)، \(2\times 2\)، و \(2\times 3\). وهذا يطابق تمامًا المضاعفية
$$\bigl(2-1+1\bigr)\bigl(3-2+1\bigr)=4.$$
وعند مسح جميع الصناديق الصالحة، يكون مجموع مضاعفياتها 32. وبإضافة المستطيلات العادية نحصل على
$$40+32=72,$$
وهي قيمة الفحص المستخدمة في تطبيقي C++ وPython.
تبدأ تطبيقات C++ وPython وJava بإعادة ترتيب البعدين بحيث يأتي الأصغر أولًا. ثم تضيف مباشرة المجموع المغلق للمستطيلات المحاذية للمحور \(\binom{N+2}{3}\binom{M+2}{3}\).
بعد ذلك تخصص التطبيقات مصفوفة مربعة من الأعداد الصحيحة تكفي لاحتواء المنطقة الماسية المزاحة \(P_{N,M}\). وكل زوج مسموح \((i,j)\) ذو التماثل الصحيح يُحوَّل إلى نقطة صحيحة، ثم يُحسب فوق مصفوفة العلامات مجموع بادئات ثنائي الأبعاد.
العمل المتبقي هو مسح شامل لكل الصناديق المحاذية للمحور في المستوى المحول. ولكل صندوق يحدد مجموع البادئات في زمن ثابت ما إذا كان الصندوق واقعًا بالكامل داخل المنطقة الماسية الصالحة. فإذا كان كذلك، تسترجع التطبيقات أبعاد الحاوية الدنيا \((h_{\min},w_{\min})\)، وتستبعد الحالات المستحيلة، ثم تضيف المضاعفية \((N-h_{\min}+1)(M-w_{\min}+1)\) إلى المجموع الجاري.
اللغات الثلاث تنفذ الرياضيات نفسها. كما يوفّر تطبيقا C++ وPython فحصًا صغيرًا عند \(3\times 2\)، بينما تحسب نسخة Java الحالة الهدف مباشرة.
الجزء المغلق الخاص بالمستطيلات المحاذية للمحور هو \(O(1)\). أما بناء مصفوفة العلامات المحولة ومجاميعها التمهيدية فيكلف \(O(M^2)\) زمنًا و \(O(M^2)\) ذاكرة، لأن طول ضلع المصفوفة هو \(2M+8\).
المرحلة المسيطرة هي المسح ذو الحلقات الأربع على جميع الصناديق المرشحة في المستوى المحول، وتكلفته \(O(M^4)\). وبالنسبة إلى الحالة الفعلية حيث \(M=47\)، فما زال ذلك عمليًا تمامًا. لذلك تكون الخوارزمية بعد التطبيع \(O(M^4)\) زمنًا و \(O(M^2)\) مساحة.