Altitud del Triángulo más grande que se puede inscribir en un Rectángulo

Posted on by Rudeus Greyrat

Dado un rectángulo de largo L y ancho B, la tarea es imprimir la máxima altura entera posible del triángulo más grande que se puede inscribir en él, tal que la altura del triángulo debe ser igual a la mitad de la base.

Ejemplos:

Entrada: L = 3, B = 4
Salida: 2

Entrada: L = 8, B = 9
Salida: 4

Entrada: L = 325, B = 300
Salida: 162

Enfoque ingenuo: el enfoque más simple es iterar sobre el rango [0, min(L, B)] a la inversa y si el valor actual es menor o igual que max(L, B) / 2 , luego imprime el valor actual como la respuesta y romper el bucle.

Complejidad temporal: O(min(L, B))
Espacio auxiliar: O(1)

Enfoque de búsqueda binaria: el enfoque anterior se puede optimizar utilizando la técnica de búsqueda binaria y observando el hecho de que siempre es óptimo seleccionar la base del triángulo en el lado con una longitud lateral máxima del rectángulo. Siga los pasos a continuación para resolver el problema:

  • Si   L es mayor que B , entonces intercambie los valores.
  • Inicialice tres variables, digamos, bajo como 0 y alto como L para realizar la búsqueda binaria en el rango [0, L].
  • Además, inicialice una variable, digamos res como 0 para almacenar la longitud máxima posible de la altitud.
  • Iterar mientras bajo es menor o igual que alto y realizar los siguientes pasos:
    • Inicialice una variable, digamos mid , y configúrela en low + (high – low) / 2 .
    • Si el valor de mid ≤ B/2 , entonces asigne mid a res y mid +1 a low .
    • De lo contrario, configure de alto a medio – 1 .
  • Finalmente, después de completar los pasos anteriores, imprima el valor obtenido en res .

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 find the greatest
// altitude of the largest triangle
// triangle that can be inscribed
// in the rectangle
int largestAltitude(int L, int B)
{
    // If L is greater than B
    if (L > B) {
        swap(B, L);
    }
 
    // Variables to perform binary
    // search
    int low = 0, high = L;
 
    // Stores the maximum altitude
    // possible
    int res = 0;
 
    // Iterate until low is less
    // than high
    while (low <= high) {
 
        // Stores the mid value
        int mid = low + (high - low) / 2;
 
        // If mide is less than
        // or equal to the B/2
        if (mid <= (B / 2)) {
 
            // Update res
            res = mid;
 
            // Update low
            low = mid + 1;
        }
        else
 
            // Update high
            high = mid - 1;
    }
 
    // Print the result
    return res;
}
 
// Driver Code
int main()
{
    // Given Input
    int L = 3;
    int B = 4;
 
    // Function call
    cout << largestAltitude(L, B);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG {
 
// Function to find the greatest
// altitude of the largest triangle
// triangle that can be inscribed
// in the rectangle
static int largestAltitude(int L, int B)
{
     
    // If L is greater than B
    if (L > B)
    {
        int t = L;
        L = B;
        B = t;
    }
   
    // Variables to perform binary
    // search
    int low = 0, high = L;
   
    // Stores the maximum altitude
    // possible
    int res = 0;
   
    // Iterate until low is less
    // than high
    while (low <= high)
    {
         
        // Stores the mid value
        int mid = low + (high - low) / 2;
   
        // If mide is less than
        // or equal to the B/2
        if (mid <= (B / 2))
        {
             
            // Update res
            res = mid;
   
            // Update low
            low = mid + 1;
        }
        else
         
            // Update high
            high = mid - 1;
    }
   
    // Print the result
    return res;
}
 
 
// Driver Code
public static void main(String[] args)
{
     // Given Input
    int L = 3;
    int B = 4;
     
    // Function call
    System.out.print(largestAltitude(L, B));
}
}
 
// This code is contributed by splevel62.

Python3

# Python 3 program for the above approach
 
# Function to find the greatest
# altitude of the largest triangle
# triangle that can be inscribed
# in the rectangle
def largestAltitude(L, B):
   
    # If L is greater than B
    if (L > B):
        temp = B
        B = L
        L = temp
 
    # Variables to perform binary
    # search
    low = 0
    high = L
 
    # Stores the maximum altitude
    # possible
    res = 0
 
    # Iterate until low is less
    # than high
    while (low <= high):
        # Stores the mid value
        mid = low + (high - low) // 2
 
        # If mide is less than
        # or equal to the B/2
        if (mid <= (B / 2)):
            # Update res
            res = mid
 
            # Update low
            low = mid + 1
 
        else:
            # Update high
            high = mid - 1
 
    # Print the result
    return res
 
# Driver Code
if __name__ == '__main__':
   
    # Given Input
    L = 3
    B = 4
 
    # Function call
    print(largestAltitude(L, B))
 
    # This code is contributed by ipg2016107.

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the greatest
// altitude of the largest triangle
// triangle that can be inscribed
// in the rectangle
static int largestAltitude(int L, int B)
{
     
    // If L is greater than B
    if (L > B)
    {
        int t = L;
        L = B;
        B = t;
    }
   
    // Variables to perform binary
    // search
    int low = 0, high = L;
   
    // Stores the maximum altitude
    // possible
    int res = 0;
   
    // Iterate until low is less
    // than high
    while (low <= high)
    {
         
        // Stores the mid value
        int mid = low + (high - low) / 2;
   
        // If mide is less than
        // or equal to the B/2
        if (mid <= (B / 2))
        {
             
            // Update res
            res = mid;
   
            // Update low
            low = mid + 1;
        }
        else
         
            // Update high
            high = mid - 1;
    }
   
    // Print the result
    return res;
}
 
// Driver Code
public static void Main(string[] args)
{
     
    // Given Input
    int L = 3;
    int B = 4;
     
    // Function call
    Console.Write(largestAltitude(L, B));
}
}
 
// This code is contributed by code_hunt

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to find the greatest
// altitude of the largest triangle
// triangle that can be inscribed
// in the rectangle
function largestAltitude(L, B) {
  // If L is greater than B
  if (L > B) {
    let temp = B;
    B = L;
    L = temp;
  }
 
  // Variables to perform binary
  // search
  let low = 0,
    high = L;
 
  // Stores the maximum altitude
  // possible
  let res = 0;
 
  // Iterate until low is less
  // than high
  while (low <= high) {
    // Stores the mid value
    let mid = Math.floor(low + (high - low) / 2);
 
    // If mide is less than
    // or equal to the B/2
    if (mid <= Math.floor(B / 2)) {
      // Update res
      res = mid;
 
      // Update low
      low = mid + 1;
    }
 
    // Update high
    else high = mid - 1;
  }
 
  // Print the result
  return res;
}
 
// Driver Code
 
// Given Input
let L = 3;
let B = 4;
 
// Function call
document.write(largestAltitude(L, B));
 
</script>
Producción

2

Complejidad de tiempo: O(log(min(L, B)))
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar aún más mediante la observación de que al colocar la base del triángulo en el lado de la longitud, max(L, B ), la altitud máxima será igual a min(max(L, B)/ 2, min(L, B)) . Siga los pasos a continuación para resolver el problema:

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 find the greatest
// altitude of the largest triangle
// triangle that can be inscribed
// in the rectangle
int largestAltitude(int L, int B)
{
    // If L is greater than B
    if (L > B)
        swap(L, B);
    // Stores the maximum altitude
    // value
    int res = min(B / 2, L);
 
    // Return res
    return res;
}
 
// Driver Code
int main()
{
    // Given Input
    int L = 3;
    int B = 4;
 
    // Function call
    cout << largestAltitude(L, B);
 
    return 0;
}

Java

// C++ program for the above approach
import java.io.*;
class GFG
{
 
// Function to find the greatest
// altitude of the largest triangle
// triangle that can be inscribed
// in the rectangle
static int largestAltitude(int L, int B)
{
   
    // If L is greater than B
    if (L > B)
        {
        int t = L;
        L = B;
        B = t;
    }
   
    // Stores the maximum altitude
    // value
    int res = Math.min(B / 2, L);
 
    // Return res
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
   
    // Given Input
    int L = 3;
    int B = 4;
 
    // Function call
    System.out.print( largestAltitude(L, B));
}
}
 
// This code is contributed by shivanisinghss2110

Python3

# Python program for the above approach
# Function to find the greatest
# altitude of the largest triangle
# triangle that can be inscribed
# in the rectangle
def largestAltitude( L,  B):
 
    # If L is greater than B
    if (L > B):
        temp = B
        B = L
        L = temp
    # Stores the maximum altitude
    # value
    res = min(B // 2, L)
 
    # Return res
    return res
 
 
# Driver Code
# Given Input
L = 3
B = 4
 
# Function call
print(largestAltitude(L, B))
 
# This ode is contributed by shivanisinghss2110

C#

// C# program for the above approach
using System;
class GFG
{
 
// Function to find the greatest
// altitude of the largest triangle
// triangle that can be inscribed
// in the rectangle
static int largestAltitude(int L, int B)
{
   
    // If L is greater than B
    if (L > B)
        {
        int t = L;
        L = B;
        B = t;
    }
   
    // Stores the maximum altitude
    // value
    int res = Math.Min(B / 2, L);
 
    // Return res
    return res;
}
 
// Driver Code
public static void Main(String[] args)
{
   
    // Given Input
    int L = 3;
    int B = 4;
 
    // Function call
    Console.Write( largestAltitude(L, B));
}
}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
// JAvascript. program for the above approach
// Function to find the greatest
// altitude of the largest triangle
// triangle that can be inscribed
// in the rectangle
function largestAltitude(L, B)
{
   
    // If L is greater than B
    if (L > B)
        {
        var t = L;
        L = B;
        B = t;
    }
   
    // Stores the maximum altitude
    // value
    var res = Math.min(B / 2, L);
 
    // Return res
    return res;
}
 
// Driver Code
    // Given Input
    var L = 3;
    var B = 4;
 
    // Function call
    document.write( largestAltitude(L, B));
 
// This code is contributed by shivanisinghss2110
</script>
Producción

2

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por subhammahato348 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 *