Dadas dos arrays X[] e Y[] , cada una de longitud 4 , donde (X[0], Y[0]) y (X[1], Y[1]) representan las esquinas inferior izquierda y superior derecha de una rectángulo y (X[2], Y[2]) y (X[3], Y[3]) representan las esquinas inferior izquierda y superior derecha del otro rectángulo, la tarea es encontrar el perímetro de los límites exteriores de la unión de los dos rectángulos como se muestra a continuación.
Ejemplos:
Entrada: X[] = {-1, 2, 0, 4}, Y[] = {2, 5, -3, 3}
Salida: 26
Explicación: Perímetro requerido = 2 * ( (4 – (-1)) + (5 – (-3)) ) = 2*(8 + 5) = 26.Entrada: X[] = {-3, 1, 1, 4}, Y[] = {-2, 3, 1, 5}
Salida: 26
Explicación: Perímetro requerido = 2 * ( (4 – (-3)) + (5 – (-2)) ) = 2*(7 + 7) = 28.
Enfoque: siga los pasos a continuación para resolver el problema:
- Comprueba si los rectángulos formados por los puntos dados se cruzan o no.
- Si se encuentra que se cruzan, entonces el perímetro se puede calcular mediante la fórmula 2*((X[1] – X[0]) + (X[3] – X[2]) + (Y[1] – Y[ 0]) + (Y[3] – Y[2])) .
- De lo contrario, imprima el doble de la suma de las diferencias máximas entre las coordenadas X e Y respectivamente, es decir, 2 * (max(X[]) – min(X[]) + max(Y[]) – min(Y[])) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if two // rectangles are intersecting or not bool doIntersect(vector<int> X, vector<int> Y) { // If one rectangle is to the // right of other's right edge if (X[0] > X[3] || X[2] > X[1]) return false; // If one rectangle is on the // top of other's top edge if (Y[0] > Y[3] || Y[2] > Y[1]) return false; return true; } // Function to return the perimeter of // the Union of Two Rectangles int getUnionPerimeter(vector<int> X, vector<int> Y) { // Stores the resultant perimeter int perimeter = 0; // If rectangles do not interesect if (!doIntersect(X, Y)) { // Perimeter of Rectangle 1 perimeter += 2 * (abs(X[1] - X[0]) + abs(Y[1] - Y[0])); // Perimeter of Rectangle 2 perimeter += 2 * (abs(X[3] - X[2]) + abs(Y[3] - Y[2])); } // If the rectangles intersect else { // Get width of combined figure int w = *max_element(X.begin(), X.end()) - *min_element(X.begin(), X.end()); // Get length of combined figure int l = *max_element(Y.begin(), Y.end()) - *min_element(Y.begin(), Y.end()); perimeter = 2 * (l + w); } // Return the perimeter return perimeter; } // Driver Code int main() { vector<int> X{ -1, 2, 4, 6 }; vector<int> Y{ 2, 5, 3, 7 }; cout << getUnionPerimeter(X, Y); }
Java
// Java program for the above approach import java.util.*; class GFG { // Function to check if two // rectangles are intersecting or not static boolean doIntersect(int []X, int []Y) { // If one rectangle is to the // right of other's right edge if (X[0] > X[3] || X[2] > X[1]) return false; // If one rectangle is on the // top of other's top edge if (Y[0] > Y[3] || Y[2] > Y[1]) return false; return true; } // Function to return the perimeter of // the Union of Two Rectangles static int getUnionPerimeter(int []X, int []Y) { // Stores the resultant perimeter int perimeter = 0; // If rectangles do not interesect if (!doIntersect(X, Y)) { // Perimeter of Rectangle 1 perimeter += 2 * (Math.abs(X[1] - X[0]) + Math.abs(Y[1] - Y[0])); // Perimeter of Rectangle 2 perimeter += 2 * (Math.abs(X[3] - X[2]) + Math.abs(Y[3] - Y[2])); } // If the rectangles intersect else { // Get width of combined figure int w = Arrays.stream(X).max().getAsInt() - Arrays.stream(X).min().getAsInt(); // Get length of combined figure int l = Arrays.stream(Y).max().getAsInt() - Arrays.stream(Y).min().getAsInt(); perimeter = 2 * (l + w); } // Return the perimeter return perimeter; } // Driver Code public static void main(String[] args) { int []X = { -1, 2, 4, 6 }; int []Y = { 2, 5, 3, 7 }; System.out.print(getUnionPerimeter(X, Y)); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to check if two # rectangles are intersecting or not def doIntersect(X, Y): # If one rectangle is to the # right of other's right edge if (X[0] > X[3] or X[2] > X[1]): return False # If one rectangle is on the # top of other's top edge if (Y[0] > Y[3] or Y[2] > Y[1]): return False return True # Function to return the perimeter of # the Union of Two Rectangles def getUnionPerimeter(X, Y): # Stores the resultant perimeter perimeter = 0 # If rectangles do not interesect if (not doIntersect(X, Y)): # Perimeter of Rectangle 1 perimeter += 2 * (abs(X[1] - X[0]) + abs(Y[1] - Y[0])) # Perimeter of Rectangle 2 perimeter += 2 * (abs(X[3] - X[2]) + abs(Y[3] - Y[2])) # If the rectangles intersect else: # Get width of combined figure w = max(X) - min(X) # Get length of combined figure l = max(Y) - min(Y) perimeter = 2 * (l + w) # Return the perimeter return perimeter # Driver Code if __name__ == '__main__': X = [ -1, 2, 4, 6] Y = [ 2, 5, 3, 7 ] print (getUnionPerimeter(X, Y)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach using System; using System.Linq; public class GFG { // Function to check if two // rectangles are intersecting or not static bool doIntersect(int []X, int []Y) { // If one rectangle is to the // right of other's right edge if (X[0] > X[3] || X[2] > X[1]) return false; // If one rectangle is on the // top of other's top edge if (Y[0] > Y[3] || Y[2] > Y[1]) return false; return true; } // Function to return the perimeter of // the Union of Two Rectangles static int getUnionPerimeter(int []X, int []Y) { // Stores the resultant perimeter int perimeter = 0; // If rectangles do not interesect if (!doIntersect(X, Y)) { // Perimeter of Rectangle 1 perimeter += 2 * (Math.Abs(X[1] - X[0]) + Math.Abs(Y[1] - Y[0])); // Perimeter of Rectangle 2 perimeter += 2 * (Math.Abs(X[3] - X[2]) + Math.Abs(Y[3] - Y[2])); } // If the rectangles intersect else { // Get width of combined figure int w = X.Max() - X.Min(); // Get length of combined figure int l = X.Max() - Y.Min(); perimeter = 2 * (l + w); } // Return the perimeter return perimeter; } // Driver Code public static void Main(String[] args) { int []X = { -1, 2, 4, 6 }; int []Y = { 2, 5, 3, 7 }; Console.Write(getUnionPerimeter(X, Y)); } } // This code contributed by shikhasingrajput
Javascript
<script> // Javascript program for the above approach // Function to check if two // rectangles are intersecting or not function doIntersect(X,Y) { // If one rectangle is to the // right of other's right edge if (X[0] > X[3] || X[2] > X[1]) return false; // If one rectangle is on the // top of other's top edge if (Y[0] > Y[3] || Y[2] > Y[1]) return false; return true; } // Function to return the perimeter of // the Union of Two Rectangles function getUnionPerimeter(X,Y) { // Stores the resultant perimeter let perimeter = 0; // If rectangles do not interesect if (!doIntersect(X, Y)) { // Perimeter of Rectangle 1 perimeter += 2 * (Math.abs(X[1] - X[0]) + Math.abs(Y[1] - Y[0])); // Perimeter of Rectangle 2 perimeter += 2 * (Math.abs(X[3] - X[2]) + Math.abs(Y[3] - Y[2])); } // If the rectangles intersect else { // Get width of combined figure let w = Math.max(...X) - Math.min(...X); // Get length of combined figure let l = Math.max(...Y) - Math.min(...Y); perimeter = 2 * (l + w); } // Return the perimeter return perimeter; } // Driver Code let X = [-1, 2, 4, 6 ]; let Y = [ 2, 5, 3, 7 ]; document.write(getUnionPerimeter(X, Y)); // This code is contributed by patel2127 </script>
24
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por the_alphaEye y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA