Número de rectángulos en la cuadrícula N*M

Nos dan una cuadrícula N*M, imprimamos el número de rectángulos en ella.
Ejemplos: 
 

Input  : N = 2, M = 2
Output : 9
There are 4 rectangles of size 1 x 1.
There are 2 rectangles of size 1 x 2
There are 2 rectangles of size 2 x 1
There is one rectangle of size 2 x 2.

Input  : N = 5, M = 4
Output : 150

Input :  N = 4, M = 3
Output: 60

Hemos discutido contar el número de cuadrados en una cuadrícula anxm . Obtengamos
una fórmula para el número de rectángulos.
Si la cuadrícula es 1×1, hay 1 rectángulo. 
Si la cuadrícula es de 2×1, habrá 2 + 1 = 3 rectángulos 
. Si la cuadrícula es de 3×1, habrá 3 + 2 + 1 = 6 rectángulos. 
podemos decir que para N*1 habrá N + (N-1) + (n-2) … + 1 = (N)(N+1)/2 rectángulos
Si le sumamos una columna más a N×1, primero tendremos tantos rectángulos en la segunda columna como en la primera, 
y luego tendremos el mismo número de rectángulos de 2×M. 
Así que N×2 = 3 (N)(N+1)/2
Después de deducir esto podemos decir 
Para N*M tendremos (M)(M+1)/2 (N)(N+1)/2 = M(M+1)(N)(N+1)/4
Entonces, la fórmula para el total de rectángulos será M(M+1)(N)(N+1)/4 

.

Lógica combinatoria:

La cuadrícula N*M se puede representar como (N+1) líneas verticales y (M+1) líneas horizontales.
En un rectángulo, necesitamos dos horizontales distintas y dos verticales distintas.
Entonces, siguiendo la lógica de las matemáticas combinatorias, podemos elegir 2 líneas verticales y 2 líneas horizontales para formar un rectángulo. Y el número total de estas combinaciones es el número de rectángulos posibles en la cuadrícula.

Número total de rectángulos en la cuadrícula N*M: ^N+1 C ₂ * ^M+1 C ₂ = (N*(N+1)/2!)*(M*(M+1)/2!) = N* (N+1)*M*(M+1)/4
 

// C++ program to count number of rectangles
// in a n x m grid
#include <bits/stdc++.h>
using namespace std;
 
int rectCount(int n, int m)
{
    return (m * n * (n + 1) * (m + 1)) / 4;
}
 
/* driver code */
int main()
{
    int n = 5, m = 4;
    cout << rectCount(n, m);
    return 0;
}

// JAVA Code to count number of
// rectangles in N*M grid
import java.util.*;
 
class GFG {
     
    public static long  rectCount(int n, int m)
    {
        return (m * n * (n + 1) * (m + 1)) / 4;
    }
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int n = 5, m = 4;
       System.out.println(rectCount(n, m));
    }
}
 
// This code is contributed by Arnav Kr. Mandal.

# Python3 program to count number
# of rectangles in a n x m grid
 
def rectCount(n, m):
 
    return (m * n * (n + 1) * (m + 1)) // 4
 
# Driver code
n, m = 5, 4
print(rectCount(n, m))
 
# This code is contributed by Anant Agarwal.

// C# Code to count number of
// rectangles in N*M grid
using System;
 
class GFG {
      
    public static long  rectCount(int n, int m)
    {
        return (m * n * (n + 1) * (m + 1)) / 4;
    }
      
    // Driver program
    public static void Main()
    {
        int n = 5, m = 4;
       Console.WriteLine(rectCount(n, m));
    }
}
  
// This code is contributed by Anant Agarwal.

<?php
// PHP program to count
// number of rectangles
// in a n x m grid
 
function rectCount($n, $m)
{
    return ($m * $n *
           ($n + 1) *
           ($m + 1)) / 4;
}
 
// Driver Code
$n = 5;
$m = 4;
echo rectCount($n, $m);
 
// This code is contributed
// by ajit
?>

<script>
 
    // Javascript Code to count number
    // of rectangles in N*M grid
     
    function rectCount(n, m)
    {
        return parseInt((m * n * (n + 1) *
                        (m + 1)) / 4, 10);
    }
     
      let n = 5, m = 4;
      document.write(rectCount(n, m));
     
</script>

Producción:  

150

Complejidad del tiempo: O(1)

Espacio Auxiliar: O(1)

Este artículo es una contribución de Pranav . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.