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