Giả sử chúng ta có một mảng các tam giác, trong đó triangles[i] = [ai, bi, ci] là ba cạnh của tam giác thứ i. Chúng ta cần sắp xếp các tam giác dựa trên diện tích của chúng. Diện tích tam giác theo ba cạnh được tính bằng công thức Heron: căn bậc hai của p*(p-a)*(p-b)*(p-c), trong đó p = (a+b+c)/2 là nửa chu vi.
Ví dụ, nếu đầu vào là (7, 24, 25), (5, 12, 13), (3, 4, 5), thì đầu ra sẽ là (3, 4, 5), (5, 12, 13), (7, 24, 25) - tức là sắp xếp theo diện tích tăng dần.
Giải thuật
- Định nghĩa cấu trúc Triangle với ba cạnh a, b, c
- Định nghĩa hàm square() tính giá trị bình phương diện tích (để tránh căn bậc hai): (a+b+c)*(a+b-c)*(a-b+c)*(-a+b+c)
- Sử dụng thuật toán sắp xếp chọn (selection sort) để sắp xếp mảng tam giác theo giá trị square() tăng dần
Ví dụ minh họa
#include <stdio.h>
#define N 3
struct Triangle {
int a, b, c;
};
int square(struct Triangle t) {
int a = t.a, b = t.b, c = t.c;
return (a + b + c) * (a + b - c) * (a - b + c) * (-a + b + c);
}
void solve(struct Triangle* a) {
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
if (square(a[i]) > square(a[j])) {
struct Triangle temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
int main() {
struct Triangle triangles[N] = {{7, 24, 25}, {5, 12, 13}, {3, 4, 5}};
solve(triangles);
for (int i = 0; i < N; i++) {
printf("(%d, %d, %d)\n", triangles[i].a, triangles[i].b, triangles[i].c);
}
return 0;
}
Đầu vào
{{7, 24, 25}, {5, 12, 13}, {3, 4, 5}}
Đầu ra
(3, 4, 5) (5, 12, 13) (7, 24, 25)