Dadas dos arrays X[] e Y[] con n elementos, donde (Xi, Yi) representan un punto en el sistema de coordenadas, encuentre el rectángulo más pequeño tal que todos los puntos de la entrada dada se encuentren dentro de ese rectángulo y los lados del rectángulo deben ser paralelos al eje de coordenadas. Imprime las cuatro coordenadas de un rectángulo obtenido.
Nota: n >= 4 (tenemos al menos 4 puntos como entrada).
Ejemplos:
Input : X[] = {1, 3, 0, 4}, y[] = {2, 1, 0, 2}
Output : {0, 0}, {0, 2}, {4, 2}, {4, 0}
Input : X[] = {3, 6, 1, 9, 13, 0, 4}, Y[] = {4, 2, 6, 5, 2, 3, 1}
Output : {0, 1}, {0, 6}, {13, 6}, {13, 1}
Para encontrar el rectángulo más pequeño, puede tomar dos enfoques básicos:
- Considere el origen del plano de coordenadas como el rectángulo más pequeño y luego, paso a paso, continúe expandiéndolo según el valor de las coordenadas de los puntos si no se encuentran dentro del rectángulo actual. Este concepto requiere un poco de lógica compleja para encontrar el rectángulo exacto más pequeño.
- Una lógica muy simple y eficiente detrás de esto es encontrar las coordenadas x e y más pequeñas y más grandes entre todos los puntos dados y luego las cuatro combinaciones posibles de estos valores dan como resultado los cuatro puntos del rectángulo requerido como {Xmin, Ymin}, {Xmin, Ymax}, {Xmax, Ymax}, {Xmax, Ymin}.
C++
// Program to find smallest rectangle
// to conquer all points
#include <bits/stdc++.h>
using namespace std;
// function to print coordinate of smallest rectangle
void printRect(int X[], int Y[], int n)
{
// find Xmax and Xmin
int Xmax = *max_element(X, X + n);
int Xmin = *min_element(X, X + n);
// find Ymax and Ymin
int Ymax = *max_element(Y, Y + n);
int Ymin = *min_element(Y, Y + n);
// print all four coordinates
cout << "{" << Xmin << ", " << Ymin << "}" << endl;
cout << "{" << Xmin << ", " << Ymax << "}" << endl;
cout << "{" << Xmax << ", " << Ymax << "}" << endl;
cout << "{" << Xmax << ", " << Ymin << "}" << endl;
}
// driver program
int main()
{
int X[] = { 4, 3, 6, 1, -1, 12 };
int Y[] = { 4, 1, 10, 3, 7, -1 };
int n = sizeof(X) / sizeof(X[0]);
printRect(X, Y, n);
return 0;
}
Java
// Program to find smallest rectangle
// to conquer all points
import java.util.Arrays;
import java.util.Collections;
class GFG {
// function to print coordinate of smallest rectangle
static void printRect(Integer X[], Integer Y[], int n)
{
// find Xmax and Xmin
int Xmax = Collections.max(Arrays.asList(X));
int Xmin = Collections.min(Arrays.asList(X));
// find Ymax and Ymin
int Ymax = Collections.max(Arrays.asList(Y));
int Ymin = Collections.min(Arrays.asList(Y));
// print all four coordinates
System.out.println("{" + Xmin + ", " + Ymin + "}");
System.out.println("{" + Xmin + ", " + Ymax + "}");
System.out.println("{" + Xmax + ", " + Ymax + "}");
System.out.println("{" + Xmax + ", " + Ymin + "}");
}
//Driver code
public static void main (String[] args)
{
Integer X[] = { 4, 3, 6, 1, -1, 12 };
Integer Y[] = { 4, 1, 10, 3, 7, -1 };
int n = X.length;
printRect(X, Y, n);
}
}
// This code is contributed by Anant Agarwal.
Python 3
# Program to find smallest rectangle
# to conquer all points
# function to print coordinate of smallest rectangle
def printRect(X, Y, n):
# find Xmax and Xmin
Xmax = max(X)
Xmin = min(X)
# find Ymax and Ymin
Ymax = max(Y)
Ymin = min(Y)
# print all four coordinates
print("{",Xmin,", ",Ymin,"}",sep="" )
print("{",Xmin,", ",Ymax,"}",sep="" )
print("{",Xmax,", ",Ymax,"}",sep="" )
print("{",Xmax,", ",Ymin,"}",sep="" )
# driver program
X = [4, 3, 6, 1, -1, 12]
Y = [4, 1, 10, 3, 7, -1]
n = len(X)
printRect(X, Y, n)
# This code is contributed by
# Smitha Dinesh Semwal
C#
// Program to find smallest rectangle
// to conquer all points
using System.Linq;
using System;
public class GFG{
// function to print coordinate
// of smallest rectangle
static void printRect(int[] X,
int[] Y, int n)
{
// find Xmax and Xmin
int Xmax = X.Max();
int Xmin = X.Min();
// find Ymax and Ymin
int Ymax = Y.Max();
int Ymin = Y.Min();
// print all four coordinates
Console.WriteLine("{" + Xmin + ", "
+ Ymin + "}");
Console.WriteLine("{" + Xmin + ", "
+ Ymax + "}");
Console.WriteLine("{" + Xmax + ", "
+ Ymax + "}");
Console.WriteLine("{" + Xmax + ", "
+ Ymin + "}");
}
// Driver code
static public void Main ()
{
int[] X = { 4, 3, 6, 1, -1, 12 };
int[] Y = { 4, 1, 10, 3, 7, -1 };
int n = X.Length;
printRect(X, Y, n);
}
}
// This code is contributed by Ajit.
PHP
<?php
// PHP Program to find smallest
// rectangle to conquer all points
// function to print coordinate
// of smallest rectangle
function printRect($X, $Y, $n)
{
// find Xmax and Xmin
$Xmax = max($X);
$Xmin = min($X);
// find Ymax and Ymin
$Ymax = max($Y);
$Ymin = min($Y);
// print all four coordinates
echo "{" , $Xmin , ", " , $Ymin , "}","\n";
echo "{" , $Xmin , ", " , $Ymax , "}" ,"\n";
echo "{" , $Xmax , ", " , $Ymax , "}","\n";
echo "{" , $Xmax , ", " , $Ymin , "}" ;
}
// Driver Code
$X = array(4, 3, 6, 1, -1, 12);
$Y = array(4, 1, 10, 3, 7, -1);
$n =count($X);
printRect($X, $Y, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Program to find smallest rectangle
// to conquer all points
// function to print coordinate of smallest rectangle
function printRect(X, Y, n)
{
// find Xmax and Xmin
var Xmax = X.reduce((a,b) => Math.max(a,b));
var Xmin = X.reduce((a,b) => Math.min(a,b));
// find Ymax and Ymin
var Ymax = Y.reduce((a,b) => Math.max(a,b));
var Ymin = Y.reduce((a,b) => Math.min(a,b));
// print all four coordinates
document.write( "{" + Xmin + ", " + Ymin + "}" + "<br>");
document.write( "{" + Xmin + ", " + Ymax + "}" + "<br>");
document.write( "{" + Xmax + ", " + Ymax + "}" + "<br>");
document.write( "{" + Xmax + ", " + Ymin + "}" + "<br>");
}
// driver program
var X = [ 4, 3, 6, 1, -1, 12 ];
var Y = [ 4, 1, 10, 3, 7, -1 ];
var n = X.length;
printRect(X, Y, n);
</script>
Producción:
{-1, -1}
{-1, 10}
{12, 10}
{12, -1}
Complejidad del tiempo: O(len(X)+len(Y))
complejidad del espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA