โปรแกรม C เรียงลำดับสามเหลี่ยมตามพื้นที่

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ของสามเหลี่ยมต่างๆ โดยที่ triangles[i] = [ai, bi, ci] แทนความยาวด้านสามด้านของสามเหลี่ยมที่ i เราต้องเรียงลำดับสามเหลี่ยมเหล่านี้ตามพื้นที่จากน้อยไปมาก พื้นที่ของสามเหลี่ยมจากความยาวด้านสามด้านคำนวณโดยสูตรของเฮอรอน (Heron's formula): รากที่สองของ p(p-a)(p-b)(p-c) โดยที่ p = (a+b+c)/2 คือกึ่งเส้นรอบรูป

ตัวอย่าง

หากอินพุตเป็น (7, 24, 25), (5, 12, 13), (3, 4, 5) ผลลัพธ์จะเป็น (3, 4, 5), (5, 12, 13), (7, 24, 25)

ขั้นตอนการแก้ปัญหา

1. กำหนดโครงสร้างข้อมูล Triangle ที่มีด้าน a, b, c
2. สร้างฟังก์ชัน square() คืนค่า 16 เท่าของพื้นที่ยกกำลังสอง (เพื่อหลีกเลี่ยงการคำนวณรากที่สอง): (a+b+c)(a+b-c)(a-b+c)(-a+b+c)
3. ใช้การเรียงลำดับแบบ Bubble Sort เปรียบเทียบค่า square() ของสามเหลี่ยมแต่ละคู่
4. สลับตำแหน่งถ้าสามเหลี่ยมด้านหน้ามีพื้นที่มากกว่า

โค้ดตัวอย่าง

#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;
}

อินพุต

{{7, 24, 25}, {5, 12, 13}, {3, 4, 5}}

เอาต์พุต

(3, 4, 5) (5, 12, 13) (7, 24, 25)