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

ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็ม งานของเราคือตรวจสอบว่าการสร้าง non-degenerate triangle โดยใช้องค์ประกอบของอาร์เรย์เป็นด้านของสามเหลี่ยมเป็นไปได้หรือไม่

Non-degenerate triangle - เป็นสามเหลี่ยมที่มีพื้นที่บวก เงื่อนไขสำหรับ non-degenerate triangle ด้วยด้าน a, b, c คือ:

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

มาดูตัวอย่างเพื่อเข้าใจปัญหาได้ดียิ่งขึ้น:

Input - arr[2, 5, 9, 4, 3]

Output - Yes

Explanation - สามเหลี่ยมที่สร้างได้คือ 2 3 4

เพื่อแก้ปัญหานี้ เราจะตรวจสอบว่าเงื่อนไขข้างต้นได้รับการปฏิบัติตามโดยค่าของอาร์เรย์

วิธีแก้แบบ navie จะเกี่ยวข้องกับการตรวจสอบทุก triplet ของอาร์เรย์โดยตรง

วิธีแก้ที่มีประสิทธิภาพมากกว่าจะเกี่ยวข้องกับการเรียงลำดับองค์ประกอบของอาร์เรย์และตรวจสอบ triplet ติดกันสามตัวของอาร์เรย์ เนื่องจากสำหรับอาร์เรย์ที่เรียงลำดับแล้ว หากผลรวมของสององค์ประกอบไม่มากกว่าตัวถัดไป การตรวจสอบค่าหลังจากนั้นก็ไม่คุ้มค่า (พวกมันใหญ่กว่าแล้ว)

ตัวอย่าง

โปรแกรมแสดงการนำโซลูชันของเราไปใช้งาน:

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

bool isTrianglePossible(int arr[], int N) {
    if (N < 3)
        return false;
    sort(arr, arr + N);
    for (int i = 0; i < N - 2; i++)
        if (arr[i] + arr[i + 1] > arr[i + 2])
            return true;
    return false;
}

int main() {
    int arr[] = {5, 12, 13, 65, 6, 1};
    int N = sizeof(arr) / sizeof(int);
    cout << "Creation of triangle from elements of array ";
    isTrianglePossible(arr, N) ? cout << "is Possible" : cout << "is not Possible";
    return 0;
}

ผลลัพธ์

Creation of triangle from elements of array is Possible