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: 6
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>
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