Encuentre el área mínima del rectángulo con un conjunto dado de coordenadas

Dada una array  de conjunto de puntos en el plano XY . La tarea es encontrar el área mínima de un rectángulo que se puede formar a partir de estos puntos. Los lados del rectángulo deben ser paralelos a los ejes X e Y. Si no se puede formar un rectángulo con los puntos dados, imprima  .
Ejemplos: 
 

Entrada: arr[][] = [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]] 
Salida: 4 
El único rectángulo posible se formará con los puntos (1, 1), (1, 3), (3, 1) y (3, 3)
Entrada: arr[][] = [[1, 1], [1, 3], [3, 1 ], [3, 3], [4, 1], [4, 3]] 
Salida: 2 
 

Aproximación: Agrupe los puntos por  coordenadas, de modo que los puntos en líneas verticales rectas se agrupen. Luego, para cada par de puntos en un grupo, por ej. coordenadas (X, Y1) y (X, Y2), buscamos el rectángulo más pequeño con este par de puntos como el borde más a la derecha del rectángulo que se va a formar. Podemos hacer esto haciendo un seguimiento de todos los otros pares de puntos que hemos visitado antes. Finalmente devuelva el área mínima posible del rectángulo obtenido.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ Implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// function to find minimum area of Rectangle
int minAreaRect(vector<vector<int>> A){
 
    // creating empty columns
    map<int,vector<int>> columns;
 
    // fill columns with coordinates
    for(auto i:A)
        columns[i[0]].push_back(i[1]);
 
    map<pair<int,int>,int > lastx;
 
    int ans = INT_MAX;
 
    for (auto x:columns)
    {
        vector<int> column = x.second;
        sort(column.begin(), column.end());
        for (int j = 0; j < column.size(); j++)
        {
            for (int i = 0; i < j; i++)
            {
                int y1 = column[i];
 
                // check if rectangle can be formed
                if (lastx.find({y1, column[j]}) != lastx.end())
                {
                    ans = min(ans, (x.first - lastx[{y1, column[j]}]) *
                            (column[j] - column[i]));
                }
                lastx[{y1, column[j]}] = x.first;
            }
            }
        }
 
    if (ans < INT_MAX)
        return ans;
    else
        return 0;
}
 
// Driver code
int main()
{
    vector<vector<int>> A = {{1, 1}, {1, 3}, {3, 1}, {3, 3}, {2, 2}};
    cout << (minAreaRect(A));
    return 0;
}
 
// This code is contributed by mohit kumar 29

/*package whatever //do not write package name here */
// Java Implementation of above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
  //# function to find minimum area of Rectangle
  public static int minAreaRect(int[][] points)
  {
 
    // creating empty columns
    @SuppressWarnings("unchecked")
    Set<Integer> columns = new HashSet();
 
    // fill columns with coordinates
    for (int[] point : points)
      columns.add(40001 * point[0] + point[1]);
 
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < points.length; ++i)
      for (int j = i + 1; j < points.length; ++j) {
        if (points[i][0] != points[j][0]
            && points[i][1] != points[j][1]) {
          if (columns.contains(40001
                               * points[i][0]
                               + points[j][1])
              && columns.contains(
                40001 * points[j][0]
                + points[i][1])) {
            ans = Math.min( ans, Math.abs(points[j][0]
                            - points[i][0])
              * Math.abs(points[j][1]
                         - points[i][1]));
          }
        }
      }
 
    return ans < Integer.MAX_VALUE ? ans : 0;
  }
   
  // Driver code
  public static void main(String[] args)
  {
 
    int[][] A = {{1, 1}, {1, 3}, {3, 1}, {3, 3}, {2, 2}};
    System.out.println(minAreaRect(A));
  }
}
 
// This code is contributed by maheshwaripiyush9

# Python Implementation of above approach
import collections
 
# function to find minimum area of Rectangle
def minAreaRect(A):
 
    # creating empty columns
    columns = collections.defaultdict(list)
 
    # fill columns with coordinates
    for x, y in A:
        columns[x].append(y)
 
    lastx = {}
    ans = float('inf')
 
    for x in sorted(columns):
        column = columns[x]
        column.sort()
        for j, y2 in enumerate(column):
            for i in range(j):
                y1 = column[i]
 
                # check if rectangle can be formed
                if (y1, y2) in lastx:
                    ans = min(ans, (x - lastx[y1, y2]) * (y2 - y1))
                lastx[y1, y2] = x
 
    if ans < float('inf'):
        return ans
    else:
        return 0
 
# Driver code
A = [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]]
print(minAreaRect(A))

<script>
/*package whatever //do not write package name here */
// Javascript Implementation of above approach
     
    //# function to find minimum area of Rectangle
    function minAreaRect(points)
    {
        // creating empty columns
    let columns = new Set();
  
    // fill columns with coordinates
    for (let point=0;point<points.length;point++)
      columns.add(40001 * points[point][0] + points[point][1]);
  
    let ans = Number.MAX_VALUE;
    for (let i = 0; i < points.length; ++i)
      for (let j = i + 1; j < points.length; ++j) {
        if (points[i][0] != points[j][0]
            && points[i][1] != points[j][1]) {
          if (columns.has(40001
                               * points[i][0]
                               + points[j][1])
              && columns.has(
                40001 * points[j][0]
                + points[i][1])) {
            ans = Math.min( ans, Math.abs(points[j][0]
                            - points[i][0])
              * Math.abs(points[j][1]
                         - points[i][1]));
          }
        }
      }
  
    return ans < Number.MAX_VALUE ? ans : 0;
    }
     
    // Driver code
    let A = [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]];
    document.write(minAreaRect(A));
     
     
// This code is contributed by patel2127
</script>

4

Complejidad de tiempo: O (N * N), ya que estamos usando bucles anidados.

Espacio auxiliar: O(N*N), ya que estamos usando espacio extra.