Área del Rectángulo más grande sin un punto dado

Dada la longitud L y la anchura B de un rectángulo y la posición de un agujero en el rectángulo como coordenada (X, Y) , la tarea es encontrar el área del rectángulo más grande dentro del rectángulo dado de modo que no contenga el agujero.
Nota: El rectángulo se coloca en el origen cuando dos de sus lados tocan el eje de coordenadas.
Ejemplos: 
 

Entrada: L = 8, B = 8, X = 0, Y = 0 
Salida: 56 
Explicación: 
Dado que el agujero está en el origen, es decir (0, 0), el rectángulo de área máxima se puede cortar desde (0, 1) o (1, 0) reduciendo el largo o el ancho del rectángulo en uno. 
Por lo tanto, el rectángulo de área máxima que se puede formar es = 7 * 8 = 56 
 

Entrada: L = 1, B = 10, X = 0, Y = 3 
Salida:
Explicación: 
Dado que el agujero está en (0, 3), el rectángulo de área máxima se puede cortar desde el punto (0, 4) reduciendo el ancho a 6 y manteniendo la longitud en 1. 
Por lo tanto, el rectángulo de área máxima que se puede formar es = 6 * 1 = 6 
 

Aproximación: Para evitar el agujero, el rectángulo se puede cortar desde arriba, abajo, a la izquierda o a la derecha del agujero, como: 
 

Position - Maximum area of rectangle
------------------------------------
Left     - X * B
Right    - (L - X - 1) * B
Above    - L * Y
Below    - (B - Y - 1) * L

Por lo tanto, el área requerida del rectángulo más grande se puede calcular comparando el área calculada usando las posiciones anteriores. La posición con el área más grande dará el resultado.
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation to find area of
// largest Rectangle without hole
// within a given Rectangle
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum area
// such that it does not contains any hole
void maximumArea(int l, int b,
                 int x, int y)
{
 
    // Area for all the possible
    // positions of the cut
    int left, right, above, below;
 
    left = x * b;
    right = (l - x - 1) * b;
    above = l * y;
    below = (b - y - 1) * l;
 
    // Find the maximum area
    // among the above rectangles
    cout << max(max(left, right),
                max(above, below));
}
 
// Driver Code
int main()
{
    int L = 8, B = 8;
    int X = 0, Y = 0;
 
    // Function call
    maximumArea(l, b, x, y);
 
    return 0;
}

Java

// Java implementation to find area of
// largest Rectangle without hole
// within a given Rectangle
import java.util.*;
 
class GFG{
  
// Function to find the maximum area
// such that it does not contains any hole
static void maximumArea(int l, int b,
                 int x, int y)
{
  
    // Area for all the possible
    // positions of the cut
    int left, right, above, below;
  
    left = x * b;
    right = (l - x - 1) * b;
    above = l * y;
    below = (b - y - 1) * l;
  
    // Find the maximum area
    // among the above rectangles
    System.out.print(Math.max(Math.max(left, right),
                Math.max(above, below)));
}
  
// Driver Code
public static void main(String[] args)
{
    int L = 8, B = 8;
    int X = 0, Y = 0;
  
    // Function call
    maximumArea(L, B, X, Y);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 implementation to find area of
# largest Rectangle without hole
# within a given Rectangle
 
# Function to find the maximum area
# such that it does not contains any hole
def maximumArea(l, b,x, y):
 
    # Area for all the possible
    # positions of the cut
    left, right, above, below = 0, 0, 0, 0
 
    left = x * b
    right = (l - x - 1) * b
    above = l * y
    below = (b - y - 1) * l
 
    # Find the maximum area
    # among the above rectangles
    print(max(max(left, right),max(above, below)))
 
# Driver Code
l = 8
b = 8
x = 0
y = 0
 
# Function call
maximumArea(l, b, x, y)
 
# This code is contributed by mohit kumar 29

C#

// C# implementation to find area of
// largest Rectangle without hole
// within a given Rectangle
using System;
 
class GFG{
   
// Function to find the maximum area
// such that it does not contains any hole
static void maximumArea(int l, int b,
                 int x, int y)
{
   
    // Area for all the possible
    // positions of the cut
    int left, right, above, below;
   
    left = x * b;
    right = (l - x - 1) * b;
    above = l * y;
    below = (b - y - 1) * l;
   
    // Find the maximum area
    // among the above rectangles
    Console.Write(Math.Max(Math.Max(left, right),
                Math.Max(above, below)));
}
   
// Driver Code
public static void Main(String[] args)
{
    int L = 8, B = 8;
    int X = 0, Y = 0;
   
    // Function call
    maximumArea(L, B, X, Y);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
      // JavaScript implementation to find area of
      // largest Rectangle without hole
      // within a given Rectangle
      // Function to find the maximum area
      // such that it does not contains any hole
      function maximumArea(l, b, x, y) {
        // Area for all the possible
        // positions of the cut
 
        var left = x * b;
        var right = (l - x - 1) * b;
        var above = l * y;
        var below = (b - y - 1) * l;
 
        // Find the maximum area
        // among the above rectangles
        document.write(Math.max(Math.max(left, right), Math.max(above, below)));
      }
 
      // Driver Code
      var L = 8,
        B = 8;
      var X = 0,
        Y = 0;
 
      // Function call
      maximumArea(L, B, X, Y);
    </script>
Producción: 

56

 

Análisis de rendimiento: 
 

  • Complejidad de tiempo: hay un cálculo simple que no implica iteraciones ni recurrencias. Por lo tanto, la Complejidad del Tiempo será O(1) .
  • Complejidad del Espacio Auxiliar: No se utiliza espacio extra. Por lo tanto, la complejidad del espacio auxiliar será O(1) .

Publicación traducida automáticamente

Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *