Recuento de rectángulos más pequeños que se pueden colocar dentro de un rectángulo más grande

Dados cuatro números enteros L, B, l y b , donde L y B denotan las dimensiones de un rectángulo más grande y l y b denotan la dimensión de un rectángulo más pequeño, la tarea es contar el número de rectángulos más pequeños que se pueden dibujar dentro un rectángulo más grande. 
Nota: los rectángulos más pequeños pueden superponerse parcialmente.

Ejemplos:

Entrada: L = 5, B = 3, l = 4, b = 1
Salida: 6
Explicación:
Hay 6 rectángulos de dimensión 4 × 1 que se pueden dibujar dentro de un rectángulo más grande de dimensión 5 × 3.

Entrada: L = 3, B = 2, l = 2, b = 1
Salida: 3
Explicación:
Hay 3 rectángulos de dimensión 3 × 2 que se pueden dibujar dentro de un rectángulo más grande de dimensión 2 × 1.

Enfoque ingenuo: la idea es iterar sobre la longitud L y la anchura B del rectángulo más grande para contar el número de rectángulos más pequeños de dimensión lxb que se pueden dibujar dentro del rango del rectángulo más grande. Imprime el conteo total después del recorrido. 
Complejidad de Tiempo: O(L * B)
Espacio Auxiliar: O(1)

Enfoque eficiente: el problema anterior se puede resolver usando permutaciones y combinaciones . A continuación se muestran los pasos:

1. Los valores posibles totales de la longitud del rectángulo más pequeño l utilizando la longitud L están dados por (L – l + 1) .
2. Los valores posibles totales del ancho del rectángulo más pequeño b usando la longitud B están dados por (B – b + 1) .
3. Por tanto, el número total de rectángulos posibles que se pueden formar viene dado por:

 
 

(L – l + 1) * (B – b + 1)

 

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count smaller rectangles
// within the larger rectangle
int No_of_rectangles(int L, int B,
                    int l, int b)
{
    // If the dimension of the smaller
    // rectangle is greater than the
    // bigger one
    if ((l > L) || (b > B)) {
        return -1;
    }
 
    else {
 
        // Return the number of smaller
        // rectangles possible
        return (L - l + 1) * (B - b + 1);
    }
}
 
// Driver Code
int main()
{
    // Dimension of bigger rectangle
    int L = 5, B = 3;
 
    // Dimension of smaller rectangle
    int l = 4, b = 1;
 
    // Function call
    cout << No_of_rectangles(L, B, l, b);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to count smaller rectangles
// within the larger rectangle
static int No_of_rectangles(int L, int B,
                            int l, int b)
{
     
    // If the dimension of the smaller
    // rectangle is greater than the
    // bigger one
    if ((l > L) || (b > B))
    {
        return -1;
    }
 
    else
    {
         
        // Return the number of smaller
        // rectangles possible
        return (L - l + 1) * (B - b + 1);
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Dimension of bigger rectangle
    int L = 5, B = 3;
 
    // Dimension of smaller rectangle
    int l = 4, b = 1;
 
    // Function call
    System.out.println(No_of_rectangles(L, B, l, b));
}
}
 
// This code is contributed by jana_sayantan

# Python3 program for the above approach
 
# Function to count smaller rectangles
# within the larger rectangle
def No_of_rectangles( L, B, l, b):
 
    # If the dimension of the smaller
    # rectangle is greater than the
    # bigger one
    if (l > L) or (b > B):
        return -1;
         
    else:
 
        # Return the number of smaller
        # rectangles possible
        return (L - l + 1) * (B - b + 1);
     
# Driver code
if __name__ == '__main__':
     
    # Dimension of bigger rectangle
    L = 5
    B = 3
 
    # Dimension of smaller rectangle
    l = 4
    b = 1
 
    # Function call
    print(No_of_rectangles(L, B, l, b))
 
# This code is contributed by jana_sayantan

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count smaller rectangles
// within the larger rectangle
static int No_of_rectangles(int L, int B,
                            int l, int b)
{
     
    // If the dimension of the smaller
    // rectangle is greater than the
    // bigger one
    if ((l > L) || (b > B))
    {
        return -1;
    }
    else
    {
         
        // Return the number of smaller
        // rectangles possible
        return (L - l + 1) * (B - b + 1);
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Dimension of bigger rectangle
    int L = 5, B = 3;
     
    // Dimension of smaller rectangle
    int l = 4, b = 1;
     
    // Function call
    Console.Write(No_of_rectangles(L, B, l, b));
}
}
 
// This code is contributed by jana_sayantan

<script>
 
// JavaScript implementation of the above approach
 
// Function to count smaller rectangles
// within the larger rectangle
function No_of_rectangles(L, B,
                            l, b)
{
       
    // If the dimension of the smaller
    // rectangle is greater than the
    // bigger one
    if ((l > L) || (b > B))
    {
        return -1;
    }
   
    else
    {
           
        // Return the number of smaller
        // rectangles possible
        return (L - l + 1) * (B - b + 1);
    }
}
 
// Driver code
         
    // Dimension of bigger rectangle
    let L = 5, B = 3;
   
    // Dimension of smaller rectangle
    let l = 4, b = 1;
   
    // Function call
    document.write(No_of_rectangles(L, B, l, b));
       
    // This code is contributed by code_hunt.
</script>

6

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)