Haga N pares de Array como punto de coordenadas (X, Y) que están encerrados dentro de un rectángulo de área mínima

Dado un número N y una array A[] de tamaño 2N , la tarea es hacer N pares de estos elementos de la array y colocarlos en un plano de coordenadas XY , de modo que estén encerrados dentro de un rectángulo de área mínima (con lados paralelos a el eje X y el eje Y ) e imprima el área del rectángulo.

Ejemplos:

Entrada: N = 4, A = {1, 4, 2, 5, 3, 6, 7, 8}
Salida: 9
Explicación: Una forma posible de hacer N pares para obtener el área mínima del rectángulo es {(1, 5), (2, 7), (3, 6), (4, 8)}
El rectángulo de área mínima se muestra en el siguiente diagrama:

Nota: Puede haber otras formas de hacer N pares de modo que el área siga siendo mínima, pero el área mínima siga siendo 9.

Entrada : N = 3, A = {1, 3, 1, 1, 2, 1}
Salida: 0

Enfoque: El área del rectángulo con la esquina inferior izquierda en (X ₁ , Y ₁ ) y la esquina superior derecha en ( X ₂ , Y ₂ ) sería (X ₂ – X ₁ )*(Y ₂ – Y ₁ ). Por lo tanto, la tarea se puede presentar como la partición de la array A en dos particiones de tamaño N, digamos X e Y , de modo que (Max(X) – Min(X)) * (Max(Y) – Min(Y)) se minimiza . Aquí, X representa las coordenadas X de los pares yY representa las coordenadas Y.

Después de clasificar A , el mínimo sería A ₁ y el máximo sería A _{2N .} Ahora bien, pueden darse los siguientes dos casos:

• Tanto A ₁ como A _2N están presentes en la misma partición, digamos X. El área del rectángulo sería (A _2N  – A ₁ ) * (Max(Y) – Min(Y)). Entonces la tarea sería minimizar Max(Y) – Min(Y). Además, si i es el índice de Min(Y) y j es el índice de Max(Y), entonces j – i >= N – 1 , ya que tiene que haber al menos N elementos en Y . Por lo tanto, es óptimo usar un segmento de tamaño N para Y (salvo que A ₁ y A _2N , como ya se han tomado),
• A ₁  y A _2N  están presentes en diferentes particiones. Para este caso, sería óptimo usar un prefijo de tamaño N y un sufijo de tamaño N como las particiones, es decir, colocar los primeros N elementos en una partición y los últimos N elementos en la otra.       

Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos, ans para almacenar el área mínima del rectángulo.
• Ordene la array A[] en orden ascendente.
• Para el primer caso :
  • Actualizar respuesta como (A[N – 1] – A[0]) * (A[2 * N – 1] – A[N]).
• Para el segundo caso :
  • Iterar en el rango [1, N-1] usando la variable i : 
    • Actualice ans como el mínimo de ans y (A[2 * N – 1] – A[0]) * (A[i + N – 1] – A[i]).
• Finalmente, regrese ans.

A continuación se muestra una implementación del código anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to make N pairs of coordinates such that they
// are enclosed in a minimum area rectangle with sides
// parallel to the X and Y axes
int minimumRectangleArea(int A[], int N)
{
    // A variable to store the answer
    int ans;
 
    sort(A, A + 2 * N);
 
    // For the case where the maximum
    // and minimum are in different partitions
    ans = (A[N - 1] - A[0]) * (A[2 * N - 1] - A[N]);
 
    // For the case where the maximum and
    // minimum are in the same partition
    for (int i = 1; i < N; i++)
        ans = min(ans, (A[2 * N - 1] - A[0])
                           * (A[i + N - 1] - A[i]));
 
    // Return the answer
    return ans;
}
 
// Driver code
int main()
{
    // Given Input
    int A[] = { 2, 4, 1, 5, 3, 6, 7, 8 };
    int N = sizeof(A) / sizeof(A[0]);
    N /= 2;
 
    // Function call
    cout << minimumRectangleArea(A, N) << endl;
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.Arrays;
 
class GFG{
     
// Function to make N pairs of coordinates
// such that they are enclosed in a minimum
// area rectangle with sides parallel to
// the X and Y axes
public static int minimumRectangleArea(int A[], int N)
{
     
    // A variable to store the answer
    int ans;
 
    Arrays.sort(A);
 
    // For the case where the maximum
    // and minimum are in different partitions
    ans = (A[N - 1] - A[0]) * (A[2 * N - 1] - A[N]);
 
    // For the case where the maximum and
    // minimum are in the same partition
    for(int i = 1; i < N; i++)
        ans = Math.min(ans, (A[2 * N - 1] - A[0]) *
                            (A[i + N - 1] - A[i]));
 
    // Return the answer
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given Input
    int A[] = { 2, 4, 1, 5, 3, 6, 7, 8 };
    int N = A.length;
    N = (int)N / 2;
 
    // Function call
    System.out.println(minimumRectangleArea(A, N));
}
}
 
// This code is contributed by lokeshpotta20

# Python3 program for the above approach
 
# Function to make N pairs of coordinates
# such that they are enclosed in a minimum
# area rectangle with sides parallel to the
# X and Y axes
def minimumRectangleArea(A, N):
     
    # A variable to store the answer
    ans = 0
 
    A.sort()
 
    # For the case where the maximum
    # and minimum are in different partitions
    ans = (A[N - 1] - A[0]) * (A[2 * N - 1] - A[N])
 
    # For the case where the maximum and
    # minimum are in the same partition
    for i in range(1, N, 1):
        ans = min(ans, (A[2 * N - 1] - A[0]) *
                       (A[i + N - 1] - A[i]))
 
    # Return the answer
    return ans
 
# Driver code
if __name__ == '__main__':
     
    # Given Input
    A = [ 2, 4, 1, 5, 3, 6, 7, 8 ]
    N = len(A)
    N //= 2
 
    # Function call
    print(minimumRectangleArea(A, N))
     
# This code is contributed by ipg2016107

// C# program for the above approach
using System;
 
class GFG{
     
// Function to make N pairs of coordinates
// such that they are enclosed in a minimum
// area rectangle with sides parallel to
// the X and Y axes
public static int minimumRectangleArea(int []A, int N)
{
     
    // A variable to store the answer
    int ans;
 
    Array.Sort(A);
 
    // For the case where the maximum
    // and minimum are in different partitions
    ans = (A[N - 1] - A[0]) * (A[2 * N - 1] - A[N]);
 
    // For the case where the maximum and
    // minimum are in the same partition
    for(int i = 1; i < N; i++)
        ans = Math.Min(ans, (A[2 * N - 1] - A[0]) *
                            (A[i + N - 1] - A[i]));
 
    // Return the answer
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Given Input
    int []A = { 2, 4, 1, 5, 3, 6, 7, 8 };
    int N = A.Length;
    N = (int)N / 2;
 
    // Function call
    Console.Write(minimumRectangleArea(A, N));
}
}
 
// This code is contributed by shivanisinghss2110

<script>
 
// JavaScript program for the above approach
 
 
// Function to make N pairs of coordinates such that they
// are enclosed in a minimum area rectangle with sides
// parallel to the X and Y axes
function minimumRectangleArea(A, N) {
// A variable to store the answer
    let ans;
 
    A.sort();
 
    // For the case where the maximum
    // and minimum are in different partitions
    ans = (A[N - 1] - A[0]) * (A[2 * N - 1] - A[N]);
 
    // For the case where the maximum and
    // minimum are in the same partition
    for (let i = 1; i < N; i++)
        ans = Math.min(ans, (A[2 * N - 1] - A[0])
            * (A[i + N - 1] - A[i]));
 
    // Return the answer
    return ans;
}
 
// Driver code
 
// Given Input
let A = [2, 4, 1, 5, 3, 6, 7, 8];
let N = A.length
N = Math.floor(N / 2);
 
// Function call
document.write(minimumRectangleArea(A, N) + "<br>");
 
</script>

9

Complejidad temporal: O(NLogN)
Espacio auxiliar: O(1)