Упорядочить стороны треугольника по возрастанию площади

Учитывая массив arr[] сторон N треугольников, задача состоит в том, чтобы отсортировать заданные стороны треугольников в порядке возрастания площади.

Примеры:

Input: arr[] = {{5, 3, 7}, {15, 20, 4}, {4, 9, 6}, {8, 4, 5}}
Output: {{5, 3, 7}, {8, 4, 5}, {4, 9, 6}, {15, 20, 17}}
Explanation:
Following are the areas of triangle:

• Area of 1st triangle (5, 3, 7) is 6.4.
• Area of 2nd triangle (15, 20, 4) is 124.2.
• Area of 3rd triangle (4, 9, 6) is 9.5.
• Area of 4th triangle (8, 4, 5) is 8.1.

Therefore, ordering them increasing order of the area modifies the given array as 6.4 {5, 3, 7}, 8.1 {8, 4, 5}, 9.5 {4, 9, 6}, 124.2 {15, 20, 4}.

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

Подход: заданное можно решить, сохранив стороны с площадью треугольника в другом массиве, а затем отсортировав массив в порядке возрастания сохраненной площади, а затем распечатав в результате стороны, сохраненные в другом массиве.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log N)
Вспомогательное пространство: O(N)

Подход, оптимизированный по пространству: описанный выше подход также может быть оптимизирован с точки зрения пространства, идея состоит в том, чтобы использовать функцию компаратора для сортировки данного массива в порядке возрастания площади. Ниже приведена функция сравнения, которая используется:

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log N)
Вспомогательное пространство: O(1)