La longitud y el ancho del rectángulo tal que la relación entre el área y la diagonal^2 es máxima

Posted on by Rudeus Greyrat

Dada una array de enteros positivos. La tarea es elegir un par de elementos de la array dada de modo que representen el largo y el ancho de un rectángulo y la relación entre su área y su diagonal 2 sea máxima. 
Nota : la array debe contener todos los lados del rectángulo. Es decir, puede elegir elementos de la array que aparecen al menos dos veces, ya que un rectángulo tiene dos lados del mismo largo y dos lados del mismo ancho.
Ejemplos: 
 

Entrada: arr[] = {4, 3, 5, 4, 3, 5, 7} 
Salida: 5, 4 
Entre todos los pares de largo y ancho 5, 4 generará la relación máxima de Área a Diámetro 2 .
Entrada: arr[] = {2, 2, 2, 2, 2, 2} 
Salida: 2, 2 
Solo hay un par posible de largo y ancho 2, 2 que generará la relación máxima de Área a Diámetro 2 .

A continuación se presentan algunas propiedades del rectángulo que deben cumplirse para formarlo. 
 

  • Un rectángulo solo se puede formar cuando tenemos al menos un par de enteros iguales. Un número entero que ocurre una vez no puede ser parte de ningún rectángulo. Entonces, en nuestra solución, consideraremos solo los números enteros cuya ocurrencia es más de una vez. 
     
  • La relación entre el área y su diámetro 2 es lb/(l 2 + b 2 ) y es una función monotónica decreciente 
    en función de una variable. Esto significa que si estamos fijando la longitud, a medida que disminuyamos el ancho, la relación obtenida disminuye y, en consecuencia, lo mismo para el ancho fijo. Aprovechando esto, no necesitamos iterar toda la array para encontrar la longitud de un ancho fijo. 
     

Algoritmo: 
 

  1. Ordenar la array dada.
  2. Cree una array (arr_pairs[]) de enteros que aparecen dos veces en la array.
  3. Establecer longitud = arr_pairs[0], amplitud = arr_pairs[0].
  4. Iterar desde i=2 hasta sizeof (arr_pairs)
    • if (largo/ancho + ancho/largo > arr_pairs[i]/arr_pairs[i-1] + arr_pairs[i-1]/arr_pairs[i])
      • actualizar longitud = arr_pairs[i], amplitud = arr_pairs[i-1]
  5. Imprimir largo y ancho.

A continuación se muestra la implementación del enfoque anterior. 
 

C++

// CPP for finding maximum
// p^2/A ratio of rectangle
#include <bits/stdc++.h>
using namespace std;
 
// function to print length and breadth
void findLandB(int arr[], int n)
{
    // sort the input array
    sort(arr, arr + n);
 
    // create array vector of integers occurring in pairs
    vector<double> arr_pairs;
    for (int i = 0; i < n; i++) {
 
        // push the same pairs
        if (arr[i] == arr[i + 1]) {
            arr_pairs.push_back(arr[i]);
            i++;
        }
    }
 
    double length = arr_pairs[0];
    double breadth = arr_pairs[1];
    double size = arr_pairs.size();
 
    // calculate length and breadth as per requirement
    for (int i = 2; i < size; i++) {
 
        // check for given condition
        if ((length / breadth + breadth / length) > (arr_pairs[i] / arr_pairs[i - 1] + arr_pairs[i - 1] / arr_pairs[i])) {
 
            length = arr_pairs[i];
            breadth = arr_pairs[i - 1];
        }
    }
 
    // print the required answer
    cout << length << ", " << breadth << endl;
}
 
// Driver Code
int main()
{
    int arr[] = { 4, 2, 2, 2, 5, 6, 5, 6, 7, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    findLandB(arr, n);
    return 0;
}

Java

// JAVA for finding maximum
// p^2/A ratio of rectangle
import java.util.*;
 
class GFG
{
 
// function to print length and breadth
static void findLandB(int arr[], int n)
{
    // sort the input array
    Arrays.sort(arr);
 
    // create array vector of integers occurring in pairs
    Vector<Double> arr_pairs = new Vector<Double>();
    for (int i = 0; i < n - 1; i++)
    {
 
        // push the same pairs
        if (arr[i] == arr[i + 1])
        {
            arr_pairs.add((double) arr[i]);
            i++;
        }
    }
 
    double length = arr_pairs.get(0);
    double breadth = arr_pairs.get(1);
    double size = arr_pairs.size();
 
    // calculate length and breadth as per requirement
    for (int i = 2; i < size; i++)
    {
 
        // check for given condition
        if ((length / breadth + breadth / length) >
            (arr_pairs.get(i) / arr_pairs.get(i - 1) +
            arr_pairs.get(i - 1) / arr_pairs.get(i)))
        {
            length = arr_pairs.get(i);
            breadth = arr_pairs.get(i - 1);
        }
    }
 
    // print the required answer
    System.out.print((int)length + ", " + (int)breadth +"\n");
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 4, 2, 2, 2, 5, 6, 5, 6, 7, 2 };
    int n = arr.length;
    findLandB(arr, n);
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python 3 for finding maximum p^2/A
# ratio of rectangle
 
# function to print length and breadth
def findLandB(arr, n):
     
    # sort the input array
    arr.sort(reverse = False)
 
    # create array vector of integers
    # occurring in pairs
    arr_pairs = []
    for i in range(n - 1):
         
        # push the same pairs
        if (arr[i] == arr[i + 1]):
            arr_pairs.append(arr[i])
            i += 1
     
    length = arr_pairs[0]
    breadth = arr_pairs[1]
    size = len(arr_pairs)
 
    # calculate length and breadth as
    # per requirement
    for i in range(1, size - 1):
         
        # check for given condition
        if ((int(length / breadth) +
             int(breadth / length)) >
            (int(arr_pairs[i] / arr_pairs[i - 1]) +
             int(arr_pairs[i - 1] / arr_pairs[i]))):
            length = arr_pairs[i]
            breadth = arr_pairs[i - 1]
 
    # print the required answer
    print(length, ",", breadth)
 
# Driver Code
if __name__== '__main__':
    arr = [4, 2, 2, 2, 5, 6, 5, 6, 7, 2]
    n = len(arr)
    findLandB(arr, n)
     
# This code is contributed by
# Surendra_Gangwar

C#

// C# for finding maximum
// p^2/A ratio of rectangle
using System;
using System.Collections.Generic;
 
class GFG
{
 
// function to print length and breadth
static void findLandB(int []arr, int n)
{
    // sort the input array
    Array.Sort(arr);
 
    // create array vector of integers occurring in pairs
    List<Double> arr_pairs = new List<Double>();
    for (int i = 0; i < n - 1; i++)
    {
 
        // push the same pairs
        if (arr[i] == arr[i + 1])
        {
            arr_pairs.Add((double) arr[i]);
            i++;
        }
    }
 
    double length = arr_pairs[0];
    double breadth = arr_pairs[1];
    double size = arr_pairs.Count;
 
    // calculate length and breadth as per requirement
    for (int i = 2; i < size; i++)
    {
 
        // check for given condition
        if ((length / breadth + breadth / length) >
            (arr_pairs[i] / arr_pairs[i - 1] +
            arr_pairs[i - 1] / arr_pairs[i]))
        {
            length = arr_pairs[i];
            breadth = arr_pairs[i - 1];
        }
    }
 
    // print the required answer
    Console.Write((int)length + ", " + (int)breadth +"\n");
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 4, 2, 2, 2, 5, 6, 5, 6, 7, 2 };
    int n = arr.Length;
    findLandB(arr, n);
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript for finding maximum
// p^2/A ratio of rectangle
 
// function to print length and breadth
function findLandB(arr, n)
{
    // sort the input array
    arr.sort();
 
    // create array vector of integers occurring in pairs
    var arr_pairs =[];
    for (var i = 0; i < n; i++) {
 
        // push the same pairs
        if (arr[i] == arr[i + 1]) {
            arr_pairs.push(arr[i]);
            i++;
        }
    }
 
    var length = arr_pairs[0];
    var breadth = arr_pairs[1];
    var size = arr_pairs.length;
 
    // calculate length and breadth as per requirement
    for (var i = 2; i < size; i++) {
 
        // check for given condition
        if ((length / breadth + breadth / length) > (arr_pairs[i] / arr_pairs[i - 1] + arr_pairs[i - 1] / arr_pairs[i])) {
 
            length = arr_pairs[i];
            breadth = arr_pairs[i - 1];
        }
    }
 
    // print the required answer
    document.write( length + ", " + breadth );
}
 
// Driver Code
var arr = [ 4, 2, 2, 2, 5, 6, 5, 6, 7, 2 ];
var n = arr.length;
findLandB(arr, n);
 
</script>
Producción: 

2, 2

 

Complejidad de tiempo: O(N * log N)
 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *