# Count of acute, obtuse and right triangles with given sides

Given an array of n positive distinct integers representing lengths of lines that can form triangle. The task is to find the number of acute triangles, obtuse triangles, and right triangles separately that can be formed from the given array.

Examples:

```Input : arr[] = { 2, 3, 9, 10, 12, 15 }.
Output :
Acute Triangle: 2
Right Triangle: 1
Obtuse Triangle: 4

Acute triangles that can be formed are {10, 12, 15}
and { 9, 10, 12 }.
Right triangles that can be formed are {9, 12, 15}.
Obtuse triangles that can be formed are {2, 9, 10},
{3, 9, 10}, {3, 10, 12} and {9, 10, 15}.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Triangle having edges a, b, c, a <= b c.
If a2 + b2 > c2, then it is acute triangle.
If a2 + b2 = c2, then it is right triangle.
If a2 + b2 < c2, then it is obtuse triangle.

Method 1 (Simple) : A brute force can be, use three loops, one for each side. Check above three conditions if a triangle is possible from three sides.

Method 2 (Efficient): An efficient approach is to first sort the array and run two loops for side a and b (a<b). Then find the farthest point q where a + b > c. So, from b to q all triangle are possible.
Also find a farthest point p where a2 + b2 >= c2.
Now, observe if a2 + b2 = c2, then increment count of right triangles. Also, acute triangle will be p – b – 1 and obtuse triangle will be q – p.

## C++

 `// C++ program to count of acute, obtuse and right ` `// triangles in an array ` `#include ` `using` `namespace` `std; ` ` `  `// Find the number of acute, right, obtuse triangle ` `// that can be formed from given array. ` `void` `findTriangle(``int` `a[], ``int` `n) ` `{ ` `    ``int` `b[n + 2]; ` ` `  `    ``// Finding the square of each element of array. ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``b[i] = a[i] * a[i]; ` ` `  `    ``// Sort the sides of array and their squares. ` `    ``sort(a, a + n); ` `    ``sort(b, b + n); ` ` `  `    ``// x for acute triangles ` `    ``// y for right triangles ` `    ``// z for obtuse triangles ` `    ``int` `x=0,y=0,z=0; ` `    ``for` `(``int` `i=0; i= c^2. ` `            ``while` `(p=b[p+1]) ` `                ``p++; ` ` `  `            ``q = max(q, p); ` ` `  `            ``// Finding the farthest point q where ` `            ``// a + b > c. ` `            ``while` `(qa[q+1]) ` `                ``q++; ` ` `  `            ``// If point p make right triangle. ` `            ``if` `(b[i]+b[j]==b[p]) ` `            ``{ ` `                ``// All triangle between j and p are acute ` `                ``// triangles. So add p - j - 1 in x. ` `                ``x += max(p - j - 1, 0); ` ` `  `                ``// Increment y by 1. ` `                ``y++; ` ` `  `                ``// All triangle between q and p are acute ` `                ``// triangles. So add q - p in z. ` `                ``z += q - p; ` `            ``} ` ` `  `            ``// If no right triangle ` `            ``else` `            ``{ ` `                ``// All triangle between j and p are acute ` `                ``// triangles. So add p - j in x. ` `                ``x += max(p - j, 0); ` ` `  `                ``// All triangle between q and p are acute ` `                ``// triangles. So add q - p in z. ` `                ``z += q - p; ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``cout << ``"Acute Triangle: "` `<< x << endl; ` `    ``cout << ``"Right Triangle: "` `<< y << endl; ` `    ``cout << ``"Obtuse Triangle: "` `<< z << endl; ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``int` `arr[] = {2, 3, 9, 10, 12, 15}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``findTriangle(arr, n); ` `    ``return` `0; ` `} `

## Python3

 `# Python3 program to count of acute, obtuse and right  ` `# triangles in an array  ` ` `  `# Find the number of acute, right, obtuse triangle  ` `# that can be formed from given array.  ` `def` `findTriangle(a, n) : ` `     `  `    ``b ``=` `[] ` `    ``# Finding the square of each element of array ` `    ``for` `i ``in` `range``(n) : ` `        ``b.append(a[i] ``*` `a[i]) ` `     `  `    ``# Sort the sides of array and their squares.  ` `    ``a.sort() ` `    ``b.sort()  ` `     `  `    ``# x for acute triangles ` `    ``# y for right triangles ` `    ``# z for obtuse triangles ` `    ``x, y, z ``=` `0``, ``0``, ``0` `     `  `    ``for` `i ``in` `range``(n) : ` `        ``p ``=` `i``+``1` `        ``q ``=` `i``+``1` `        ``for` `j ``in` `range``(i ``+` `1``, n) : ` `            ``# Finding the farthest point p where ` `            ``# a^2 + b^2 >= c^2. ` `            ``while` `(p``=``b[p``+``1``]) : ` `                ``p ``+``=` `1` `            ``q ``=` `max``(q, p) ` `            ``# Finding the farthest point q where  ` `            ``# a + b > c. ` `            ``while` `(qa[q``+``1``]) : ` `                ``q ``+``=` `1` `                 `  `            ``# If point p make right triangle. ` `            ``if` `(b[i]``+``b[j]``=``=``b[p]) : ` `                ``# All triangle between j and p are acute ` `                ``# triangles. So add p - j - 1 in x. ` `                ``x ``+``=` `max``(p ``-` `j ``-` `1``, ``0``) ` `                ``# Increment y by 1. ` `                ``y ``+``=` `1`  `                ``# All triangle between q and p are acute ` `                ``# triangles. So add q - p in z. ` `                ``z ``+``=` `q ``-` `p ` `            ``# If no right triangle ` `            ``else` `: ` `                ``# All triangle between j and p are acute ` `                ``# triangles. So add p - j in x. ` `                ``x ``+``=` `max``(p ``-` `j, ``0``) ` `                ``# All triangle between q and p are acute  ` `                ``# triangles. So add q - p in z. ` `                ``z ``+``=` `q ``-` `p ` `     `  `    ``print``(``"Acute Triangle:"``,x ) ` `    ``print``(``"Right Triangle:"``, y)  ` `    ``print``(``"Obtuse Triangle:"``, z)  ` ` `  ` `  `# Driver Code  ` `if` `__name__ ``=``=` `"__main__"` `: ` ` `  `    ``arr ``=` `[``2``, ``3``, ``9``, ``10``, ``12``, ``15``] ` `    ``n ``=` `len``(arr) ` `    ``findTriangle(arr, n) ` ` `  `# This code is contributed by Ryuga `

## PHP

 `= c^2. ` `            ``while` `(``\$p` `< ``\$n` `- 1 && ` `                   ``\$b``[``\$i``] + ``\$b``[``\$j``] >= ``\$b``[``\$p` `+ 1]) ` `                ``\$p``++; ` ` `  `            ``\$q` `= max(``\$q``, ``\$p``); ` ` `  `            ``// Finding the farthest point q  ` `            ``// where a + b > c. ` `            ``while` `(``\$q` `< ``\$n` `- 1 &&  ` `                   ``\$a``[``\$i``] + ``\$a``[``\$j``] > ``\$a``[``\$q` `+ 1]) ` `                ``\$q``++; ` ` `  `            ``// If point p make right triangle. ` `            ``if` `(``\$b``[``\$i``] + ``\$b``[``\$j``] == ``\$b``[``\$p``]) ` `            ``{ ` `                ``// All triangle between j and p are acute ` `                ``// triangles. So add p - j - 1 in x. ` `                ``\$x` `+= max(``\$p` `- ``\$j` `- 1, 0); ` ` `  `                ``// Increment y by 1. ` `                ``\$y``++; ` ` `  `                ``// All triangle between q and p are ` `                ``// acute triangles. So add q - p in z. ` `                ``\$z` `+= ``\$q` `- ``\$p``; ` `            ``} ` ` `  `            ``// If no right triangle ` `            ``else` `            ``{ ` `                ``// All triangle between j and p are acute ` `                ``// triangles. So add p - j in x. ` `                ``\$x` `+= max(``\$p` `- ``\$j``, 0); ` ` `  `                ``// All triangle between q and p are acute ` `                ``// triangles. So add q - p in z. ` `                ``\$z` `+= ``\$q` `- ``\$p``; ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``echo` `"Acute Triangle: "``, ``\$x``, ````" "````; ` `    ``echo` `"Right Triangle: "``, ``\$y``, ````" "````; ` `    ``echo` `"Obtuse Triangle: "``, ``\$z``, ````" "````; ` `} ` ` `  `// Driver Code ` `\$arr` `= ``array``(2, 3, 9, 10, 12, 15); ` `\$n` `= sizeof(``\$arr``); ` `findTriangle(``\$arr``, ``\$n``); ` ` `  `// This code is contributed by akt_mit ` `?> `

Output:

```Acute Triangle: 2
Right Triangle: 1
Obtuse Triangle: 4
```

## tags:

Geometric Geometric