Cuente la cantidad de rombos posibles dentro de un rectángulo de tamaño dado

Dado un rectángulo de altura H y ancho W que tiene la esquina inferior izquierda en (0, 0) . La tarea es contar el número de rombos distintos que tienen todos los puntos dentro o en el borde del rectángulo que cumple las siguientes condiciones: 
 

• Tener área distinta de cero.
• Tienen diagonales paralelas a los ejes x e y.
• Tener coordenadas enteras.

Ejemplos: 
 

Entrada: H = 2, W = 2 
Salida: 2 
Solo es posible un rombo con coordenadas (0, 1), (1, 0), (2, 1) y (1, 2). 
 

Entrada: H = 4, W = 4 
Salida: 16 
 

Enfoque: dado que las diagonales son paralelas al eje, intentemos arreglar las diagonales y crear rombos en ellas. Para que el rombo tenga coordenadas enteras, la longitud de las diagonales debe ser par. Fijemos la longitud de las diagonales a i y j , el número de rombos que podemos formar con estas longitudes de diagonal dentro del rectángulo sería (H – i + 1) * (W – j + 1) . Por lo tanto, iteramos sobre todos los valores posibles de i y j y actualizamos el conteo.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of rhombi possible
long long countRhombi(int h, int w)
{
    long long ct = 0;
 
    // All possible diagonal lengths
    for (int i = 2; i <= h; i += 2)
        for (int j = 2; j <= w; j += 2)
 
            // Update rhombi possible with
            // the current diagonal lengths
            ct += (h - i + 1) * (w - j + 1);
 
    // Return the total count
    // of rhombi possible
    return ct;
}
 
// Driver code
int main()
{
    int h = 2, w = 2;
 
    cout << countRhombi(h, w);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
     
// Function to return the count of rhombi possible
static int countRhombi(int h, int w)
{
    int ct = 0;
 
    // All possible diagonal lengths
    for (int i = 2; i <= h; i += 2)
        for (int j = 2; j <= w; j += 2)
 
            // Update rhombi possible with
            // the current diagonal lengths
            ct += (h - i + 1) * (w - j + 1);
 
    // Return the total count
    // of rhombi possible
    return ct;
}
 
    // Driver code
    public static void main (String[] args)
    {
    int h = 2, w = 2;
    System.out.println (countRhombi(h, w));
    }
}
 
// This code is contributed by jit_t

# Python 3 implementation of the approach
 
# Function to return the count of
# rhombi possible
def countRhombi(h, w):
 
    ct = 0;
 
    # All possible diagonal lengths
    for i in range(2, h + 1, 2):
        for j in range(2, w + 1, 2):
 
            # Update rhombi possible with
            # the current diagonal lengths
            ct += (h - i + 1) * (w - j + 1)
 
    # Return the total count
    # of rhombi possible
    return ct
 
# Driver code
if __name__ == "__main__":
 
    h = 2
    w = 2
 
    print(countRhombi(h, w))
 
# This code is contributed by ita_c

// C# program to find the frequency of
// minimum element in the array
using System;
 
class GFG
{
         
    // Function to return the count
    // of rhombi possible
    static int countRhombi(int h, int w)
    {
        int ct = 0;
     
        // All possible diagonal lengths
        for (int i = 2; i <= h; i += 2)
            for (int j = 2; j <= w; j += 2)
     
                // Update rhombi possible with
                // the current diagonal lengths
                ct += (h - i + 1) * (w - j + 1);
     
        // Return the total count
        // of rhombi possible
        return ct;
    }
     
    // Driver code
    public static void Main()
    {
        int h = 2, w = 2;
         
        Console.WriteLine(countRhombi(h, w));
    }
}
 
// This code is contributed by Ryuga

<?php
// PHP implementation of the approach
 
// Function to return the count of
// rhombi possible
function countRhombi($h, $w)
{
    $ct = 0;
 
    // All possible diagonal lengths
    for ($i = 2; $i <= $h; $i += 2)
        for ($j = 2; $j <= $w; $j += 2)
 
            // Update rhombi possible with
            // the current diagonal lengths
            $ct += ($h - $i + 1) * ($w - $j + 1);
 
    // Return the total count
    // of rhombi possible
    return $ct;
}
 
// Driver code
$h = 2; $w = 2;
echo(countRhombi($h, $w));
 
// This code is contributed by Code_Mech
?>

<script>
    // Javascript program to find the frequency of
    // minimum element in the array 
     
    // Function to return the count
    // of rhombi possible
    function countRhombi(h, w)
    {
        let ct = 0;
       
        // All possible diagonal lengths
        for (let i = 2; i <= h; i += 2)
            for (let j = 2; j <= w; j += 2)
       
                // Update rhombi possible with
                // the current diagonal lengths
                ct += (h - i + 1) * (w - j + 1);
       
        // Return the total count
        // of rhombi possible
        return ct;
    }
     
    let h = 2, w = 2;
           
      document.write(countRhombi(h, w));
     
</script>

1

Complejidad del tiempo: O(H * W)

Espacio Auxiliar: O(1)