Count Acute, Right and Obtuse triangles from n side lengths Problem Statement: We have \$N\$ sticks. The size of the \$i\$th stick is \$A_i\$. We want to know the number of different types of triangles created with each side from a single different stick. Calculate the number of acute triangles, right triangles and obtuse triangles.

Input Format: The first line contains \$N\$. The second line contains \$N\$ integers. The \$i\$th number denotes \$A_i\$.

Constraints:


For full score: \$3 \le N \le 5000\$
For 40% score: \$3 \le N \le 500\$


For all test cases:


\$1 \le A[i] \le 10^4\$
\$A[i] \lt A[i+1]\$ where \$1 \le i \lt N\$


Output Format: Print 3 integers: the number of acute triangles, right triangles and obtuse triangles, respectively.

My Solution: My code runs in the given time for small \$n\$ (~500). It will work for large \$n\$ (~5000) but I get time limit exceeded error on the Online Judge.

using System;

namespace CodeStorm
{
    class Triangles
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] A_temp = Console.ReadLine().Split(' ');
            int[] A = Array.ConvertAll(A_temp, Int32.Parse);
            int[] A_sq = new int[n];

            for (int i = 0; i &lt; n; i++)
            {
                A_sq[i] = A[i] * A[i];
            }

            int n_m_2 = n - 2;
            int n_m_1 = n - 1;

            int acute = 0, right = 0, obtuse = 0;
            for (int i = 0; i &lt; n_m_2; i++)
            {
                for (int j = i + 1; j &lt; n_m_1; j++)
                {
                    int k = j + 1;
                    int AiPlusAj = A[i] + A[j];

                    while (k &lt; n)
                    {
                        int squareSum = A_sq[i] + A_sq[j];
                        if (AiPlusAj &lt;= A[k])
                        {
                            break;
                        }
                        else if (squareSum &gt; A_sq[k])
                        {
                            acute++;
                        }
                        else if (squareSum &lt; A_sq[k])
                        {
                            obtuse++;
                        }
                        else
                        {
                            right++;
                        }
                        k++;
                    }
                }
            }
            Console.WriteLine(acute + " " + right + " " + obtuse);
            Console.ReadLine();
        }
    }
}


The above code runs perfectly and finds the possible triangles.

Input:

6    
2 3 9 10 12 15


Output:

2 1 4


The possible triangles are:


  Acute triangles: 10−12−15, 9−10−12
  
  Right triangle: 9−12−15
  
  Obtuse triangles: 2−9−10, 3−9−10, 3−10−12, 9−10−15


I want to know a more efficient way to approach the problem so that I can get it executed in the given time limit for \$n\$ (~5000). After I tried to find the complexity, I came up with \$O(n^3)\$. I am not good with complexities. I might be wrong. I would like a more efficient way for the problem.
Sort your sticks by length; square them when already sorted. Then replace the innermost loop with 3 binary searches. In pseudocode,

        max_obtuse = upper_bound(A[j:n], A[i] + A[j])
        max_right = upper_bound(A_sq[j:n], A_sq[i] + A_sq[j])
        max_acute = lower_bound(A_sq[j:n], A_sq[i] + A_sq[j])

        obtuse += max_obtuse - max_right
        right += max_right - max_acute
        acute += max_acute - j


That reduces the execution time from \$O(n^3)\$ to \$O(n^2\log n)\$.

EDIT:

In the sorted array below, values marked as - are strictly less, and values marked as + are strictly greater, than X:

    -----XXXXXXXXXXXXXXXXX++++++++++
         ^                ^
         |                This is upper bound of X
         This is lower bound of X