Ordenar los lados del triángulo en función del área creciente

Dada una array arr[] de lados de N triángulos, la tarea es ordenar los lados dados de los triángulos sobre la base del orden creciente del área.

Ejemplos:

Entrada: arr[] = {{5, 3, 7}, {15, 20, 4}, {4, 9, 6}, {8, 4, 5}}
Salida: {{5, 3, 7}, {8, 4, 5}, {4, 9, 6}, {15, 20, 17}}
Explicación: Las
siguientes son las áreas del triángulo:

  • El área del primer triángulo (5, 3, 7) es 6,4.
  • El área del segundo triángulo (15, 20, 4) es 124,2.
  • El área del tercer triángulo (4, 9, 6) es 9,5.
  • El área del cuarto triángulo (8, 4, 5) es 8,1.

Por lo tanto, ordenarlos en orden creciente del área modifica la array dada como 6.4 {5, 3, 7}, 8.1 {8, 4, 5}, 9.5 {4, 9, 6}, 124.2 {15, 20, 4}.

Entrada: arr[] = {{7, 24, 25}, {5, 12, 13}, {3, 4, 5}}
Salida: {{3, 4, 5}, {5, 12, 13}, {7, 24, 25}}

Enfoque: lo dado se puede resolver almacenando los lados con el área del triángulo en otra array y luego ordenar la array en orden creciente de área almacenada y luego imprimir los lados almacenados en otra array como resultado.

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 rearrange the sides of
// triangle in increasing order of area
void rearrangeTriangle(
    vector<vector<int> > arr, int N)
{
    // Stores the area of triangles with
    // their corresponding indices
    vector<pair<float, int> > area;
 
    for (int i = 0; i < N; i++) {
 
        // Find the area
        float a = (arr[i][0]
                   + arr[i][1]
                   + arr[i][2])
                  / 2.0;
        float Area = sqrt(abs(a * (a - arr[i][0])
                              * (a - arr[i][1])
                              * (a - arr[i][2])));
 
        area.push_back({ Area, i });
    }
 
    // Sort the area vector
    sort(area.begin(), area.end());
 
    // Resultant sides
    for (int i = 0; i < area.size(); i++) {
        cout << arr[area[i].second][0]
             << " "
             << arr[area[i].second][1]
             << " "
             << arr[area[i].second][2]
             << '\n';
    }
}
 
// Driver Code
int main()
{
    vector<vector<int> > arr = {
        { 5, 3, 7 }, { 15, 20, 4 }, { 4, 9, 6 }, { 8, 4, 5 }
    };
    int N = arr.size();
 
    rearrangeTriangle(arr, N);
 
    return 0;
}

Python3

# python program for the above approach
import math
 
# Function to rearrange the sides of
# triangle in increasing order of area
def rearrangeTriangle(arr, N):
 
        # Stores the area of triangles with
        # their corresponding indices
    area = []
 
    for i in range(0, N):
 
                # Find the area
        a = (arr[i][0] + arr[i][1] + arr[i][2]) / 2.0
        Area = math.sqrt(
            abs(a * (a - arr[i][0]) * (a - arr[i][1]) * (a - arr[i][2])))
 
        area.append([Area, i])
 
        # Sort the area vector
    area.sort()
 
    # Resultant sides
    for i in range(0, len(area)):
        print(arr[area[i][1]][0], end=" ")
        print(arr[area[i][1]][1], end=" ")
        print(arr[area[i][1]][2])
 
# Driver Code
if __name__ == "__main__":
 
    arr = [
        [5, 3, 7], [15, 20, 4], [4, 9, 6], [8, 4, 5]
    ]
    N = len(arr)
 
    rearrangeTriangle(arr, N)
 
    # This code is contributed by rakeshsahni

C#

// C# implementation for the above approach
using System;
using System.Collections.Generic;
 
class GFG {
 
  // Function to rearrange the sides of
  // triangle in increasing order of area
  static void rearrangeTriangle(
    List<List<int> > arr, int N)
  {
     
    // Stores the area of triangles with
    // their corresponding indices
    List<KeyValuePair<float, int> > area = new List<KeyValuePair<float, int> >();
 
    for (int i = 0; i < N; i++) {
 
      // Find the area
      float a = (float)(arr[i][0]
                        + arr[i][1]
                        + arr[i][2])
        / 2;
      float Area = (float)Math.Sqrt(Math.Abs(a * (a - arr[i][0])
                                             * (a - arr[i][1])
                                             * (a - arr[i][2])));
 
      area.Add(new KeyValuePair <float, int>(Area, i ));
    }
 
    // Sort the area List
    area.Sort((x, y) => x.Key.CompareTo(y.Key));
 
    // Resultant sides
    for (int i = 0; i < area.Count; i++) {
      Console.WriteLine(arr[area[i].Value][0] + " "
                        + arr[area[i].Value][1]
                        + " "
                        + arr[area[i].Value][2]);
    }
  }
 
  // Driver Code
  static public void Main ()
  {
    List<List<int> > arr = new List<List<int> >(){
      new List<int>(){ 5, 3, 7 },
      new List<int>(){ 15, 20, 4 },
      new List<int>(){ 4, 9, 6 },
      new List<int>(){ 8, 4, 5 }
    };
    int N = arr.Count;
 
    rearrangeTriangle(arr, N);
  }
}
 
// This code is contributed
// by Shubham Singh

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to rearrange the sides of
        // triangle in increasing order of area
        function rearrangeTriangle(
            arr, N)
        {
         
            // Stores the area of triangles with
            // their corresponding indices
            let area = [];
 
            for (let i = 0; i < N; i++) {
 
                // Find the area
                let a = (arr[i][0]
                    + arr[i][1]
                    + arr[i][2])
                    / 2.0;
                let Area = Math.sqrt(Math.abs(a * (a - arr[i][0])
                    * (a - arr[i][1])
                    * (a - arr[i][2])));
 
                area.push({ first: parseInt(Area), second: parseInt(i) });
            }
 
            // Sort the area vector
            area.sort(function (a, b) {
                return a.first - b.first;
            })
 
            // Resultant sides
            for (let i = 0; i < area.length; i++) {
                document.write(arr[area[i].second][0]
                    + " "
                    + arr[area[i].second][1]
                    + " "
                    + arr[area[i].second][2]
                    + '<br>'
                )
            }
        }
 
        // Driver Code
        let arr = [
            [5, 3, 7], [15, 20, 4], [4, 9, 6], [8, 4, 5]
        ];
        let N = arr.length;
        rearrangeTriangle(arr, N);
 
       // This code is contributed by Potta Lokesh
 
    </script>
Producción: 

5 3 7
8 4 5
4 9 6
15 20 4

 

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)

Enfoque de espacio optimizado: el enfoque anterior también se puede optimizar en términos de espacio, la idea es usar la función de comparación para ordenar la array dada en orden creciente de área. A continuación se muestra la función de comparación que se utiliza:

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 area of sides
// of triangle stored in arr[]
float findArea(vector<int>& arr)
{
 
    // Find the semi perimeter
    float a = (arr[0]
               + arr[1]
               + arr[2])
              / 2.0;
 
    // Find area using Heron's Formula
    float Area = sqrt(abs(a * (a - arr[0])
                          * (a - arr[1])
                          * (a - arr[2])));
 
    // Return the area
    return Area;
}
 
// Comparator function to sort the given
// array of sides of triangles in
// increasing order of area
bool cmp(vector<int>& A, vector<int>& B)
{
    return findArea(A) <= findArea(B);
}
 
// Function to rearrange the sides of
// triangle in increasing order of area
void rearrangeTriangle(
    vector<vector<int> > arr, int N)
{
    // Sort the array arr[] in increasing
    // order of area
    sort(arr.begin(), arr.end(), cmp);
 
    // Resultant sides
    for (int i = 0; i < N; i++) {
        cout << arr[i][0] << " " << arr[i][1] << " "
             << arr[i][2] << '\n';
    }
}
 
// Driver Code
int main()
{
    vector<vector<int> > arr = {
        { 5, 3, 7 }, { 15, 20, 4 }, { 4, 9, 6 }, { 8, 4, 5 }
    };
    int N = arr.size();
 
    rearrangeTriangle(arr, N);
 
    return 0;
}

Python3

# Python program for the above approach
import math
 
# Function to find the area of sides
# of triangle stored in arr[]
def findArea(arr):
 
    # Find the semi perimeter
    a = (arr[0] + arr[1] + arr[2]) / 2.0
     
    # Find area using Heron's Formula
    Area = math.sqrt(abs(a * (a - arr[0]) * (a - arr[1]) * (a - arr[2])))
     
    # Return the area
    return Area
   
# Function to rearrange the sides of
# triangle in increasing order of area
def rearrangeTriangle(arr , N):
   
  # Sort the array arr[] in increasing
  # order of area
  arr.sort(key = lambda x: (findArea(x)))
   
  # Resultant sides
  for i in range(0,N):
    print(arr[i][0], arr[i][1], arr[i][2])
              
# Driver Code
if __name__ == "__main__":
 
    arr = [[5 , 3 , 7], [15 , 20 , 4], [4 , 9 , 6], [8 , 4 , 5]]
    N = len(arr)
     
    rearrangeTriangle(arr, N)
     
    # This code is contributed by bhupenderyadav18.

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
         
        // Function to find the area of sides
        // of triangle stored in arr[]
       function findArea(arr)
       {
  
         // Find the semi perimeter
         let a = (arr[0] + arr[1] + arr[2]) / 2.0;
  
         // Find area using Heron's Formula
         let Area = Math.sqrt(Math.abs(a * (a - arr[0]) * (a - arr[1])* (a - arr[2])));
  
         // Return the area
         return Area;
        }
         
        // Comparator function to sort the given
        // array of sides of triangles in
        // increasing order of area
        function cmp(A, B)
        {
            return findArea(A) - findArea(B);
        }
         
 
        // Function to rearrange the sides of
        // triangle in increasing order of area
        function rearrangeTriangle(arr, N)
        {
            // Sort the array arr[] in increasing
            // order of area
            arr.sort(function (a, b) {
                return cmp(a,b);
            })
 
            // Resultant sides
            for (let i = 0; i < N; i++) {
                document.write(arr[i][0]
                    + " "
                    + arr[i][1]
                    + " "
                    + arr[i][2]
                    + '<br>'
                )
            }
        }
 
        // Driver Code
        let arr = [
            [5, 3, 7], [15, 20, 4], [4, 9, 6], [8, 4, 5]
        ];
        let N = arr.length;
        rearrangeTriangle(arr, N);
 
    // This code is contributed by Pushpesh Raj
 
    </script>
Producción: 

5 3 7
8 4 5
4 9 6
15 20 4

 

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

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