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  A_sq[k])
                        {
                            acute++;
                        }
                        else if (squareSum < 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 tria

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

StackExchange Code Review Q#109243, answer score: 5