นับจำนวนสามเหลี่ยมที่เป็นไปได้จากอาร์เรย์ความยาวด้าน ใน C++

ได้รับอาร์เรย์ที่เก็บความยาวด้านของสามเหลี่ยม ต้องการนับจำนวนสามเหลี่ยมที่สร้างได้จากการเลือก 3 ด้านใดๆ

เงื่อนไขสามเหลี่ยม

ผลรวมของด้านใดๆ 2 ด้าน ต้องมากกว่าด้านที่ 3 ทุกคู่

a + b > c, a + c > b, b + c > a

ตัวอย่าง

อินพุต: arr[] = {1, 2, 4, 5}

เอาต์พุต: 1 (ด้าน 2,4,5)

อินพุต: arr[] = {4, 5, 6, 3, 2}

เอาต์พุต: 7

แนวทาง

• ลูป 3 ชั้น i=0..n-3, j=i+1..n-2, k=j+1..n-1
• ตรวจสอบเงื่อนไขสามเหลี่ยมทั้ง 3 ข้อ

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

#include <bits/stdc++.h>
using namespace std;

int countTriangles(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n-2; i++) {
        for (int j = i+1; j < n-1; j++) {
            for (int k = j+1; k < n; k++) {
                if (arr[i] + arr[j] > arr[k] && 
                    arr[i] + arr[k] > arr[j] && 
                    arr[k] + arr[j] > arr[i]) {
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    int Arr[] = {1, 2, 5, 3, 6, 8, 10};
    int len = sizeof(Arr) / sizeof(Arr[0]);
    cout << "count of Triangles possible: " << countTriangles(Arr, len);
    return 0;
}

ผลลัพธ์

count of Triangles possible: 8