Find the number of possible pairs of hypotenuses and areas of a right triangle using C++ programming

In this article we will explain how to find the number of possible pairs of hypotenuse and area that form a right triangle in C.

We need to determine the number of all possible pairs of a hypotenuse and area ( H, A ) forming a right triangle where H is the hypotenuse and A is the area.

In this example-

          x = base of the right triangle

      y = height of the right triangle

       H = hypotenuse of the right triangle

We know the area of ​​a right triangle,

A = ( x * y ) / 2

or

4 * A² = ( x * y )² … ... (1)

We also know

x² y² =H ² …… (2)

Solution (1) & (2)

4 * A² = x² ( H ² - x² )

Solve the quadratic equation in x2 and let D (discriminant) >= 0 (x exists)

We get, H2 >= 4 * A (condition for the existence of a right triangle)

Here is the example-

Input : array H[ ] = { 3, 6, 8 } : A[ ] = { 2, 31, 12 }
Output : 4
Explanation : possible pairs of Hypotenuse and Area ( H, A ) are ( 3, 2 ), ( 6, 2 ), ( 8, 2 ) and ( 8, 12 ).

Input : array H[ ] = { 2, 5, 9 } : A[ ] = { 3, 11, 7 }
Output : 4
Explanation : possible pairs of Hypotenuse and Area ( H, A ) are possible pairs of Hypotenuse and Area ( H, A ) are ( 5, 3 ), ( 9, 3 ), ( 9, 11 ) and ( 9, 7 ).

Solution method

Now we Two different methods will be used to perform the given task -

Brute force method

In this simple method we find all possible hypotenuses and areas (H,A ), check whether they satisfy the condition h2 >= 4 * A, and count the number of each pair of combinations that satisfy this condition.

Example

#include <iostream>
using namespace std;
int main(){
    int H[ ] = { 2,5,9}; // array of hypotenuse
    int s1 = sizeof(H)/sizeof(H[0]);
    int A[ ] = { 3, 11, 7};// array of area
    int s2 = sizeof(A)/sizeof(A[0]);
    int count = 0;// initialising count to 0
    // finding all possible pairs
    for (int i = 0; i < s1; i++) {
        for (int j = 0; j < s2; j++) {
            // checking whether current pair satisfies the condition
            if (H[i] * H[i] >= 4 * A[j]){
                count++;

            }
        }
    }
    cout << "Number of possible pairs of ( H, A ): " << count ;
    return 0;
}

Output

Number of possible pairs of ( H, A ): 4

Explanation

In this code, we use a count variable to hold the number of pairs that satisfy the equation, and use embedding A set of loops generates (H, A) pairs. The time complexity of this code is O(n2), which is not an efficient approach. Let's understand the second method.

Efficient method

In this method we first sort both arrays in ascending order and then find the maximum area check by finding any hypotenuse lengthH ² > 4*A.

Example

#include <bits/stdc++.h>
using namespace std;
int main (){
    int H[] = { 2, 5, 9 };
    int s1 = sizeof (H) / sizeof (H[0]);
    int A[] = {  3, 11, 7 };
    int s2 = sizeof (A) / sizeof (A[0]);
    int count = 0;
    // Sorting both the arrays
    sort (H, H + s1);
    sort (A, A + s2);
    int temp = -1;
    for (int i = 0; i < s1; i++){
        // Applying binary search for
        // every Hypotenuse Length
        int flag1 = 0;
        int flag2 = s2 - 1;
        while (flag1 <= flag2){
            int mid = flag1 + (flag2 - flag1) / 2;
            if ((H[i] * H[i]) >= (4 * A[mid])){
                temp = mid;
                flag1 = mid + 1;
            }
            else{
                flag2 = mid - 1;
            }
        }
        if (temp != -1){// Check if we get any possible area
            count += temp + 1;
        }
    }
    cout << "Number of possible pairs of (H, A): " << count;
    return 0;
}

Output

Number of possible pairs of ( H, A ): 4

Explanation of the above code

In this code, we first sort the two arrays in ascending order and then use Binary search checks every possible length to find the largest region.

Suppose the maximum area is found at index 3 in the array of region A[ ], then all regions smaller than index 3 also satisfy this equation, so we can form 3 possible pairs.

>

Conclusion

In this article we solved the problem of finding the number of hypotenuse and area pairs used to form a right triangle. We applied a brute force approach, which has a time complexity of O(n²), and an efficient approach, which has a time complexity of O(s1 log(s2)). Hope this article is helpful to you.

The above is the detailed content of Find the number of possible pairs of hypotenuses and areas of a right triangle using C++ programming. For more information, please follow other related articles on the PHP Chinese website!