joel's sticks

Joel has a collection of sticks of different sizes. He wants to know how many various kinds of triangles (acute, right, and obtuse) he can create using these sticks.

Input Format

The first line contains , the number of sticks. The next line contains integers separated by spaces denoting the length of the sticks in ascending order of length.

Constraints

Output Format

Print the total number of acute, right, and obtuse triangles respectively separated by spaces.

Sample Input 0

5
1 2 3 4 5

Sample Output 0

0 1 2

Solution

Solution by Kalana Liyanage

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void countTriangles(vector<int>& sticks) {
    int n = sticks.size();
    sort(sticks.begin(), sticks.end());
    vector<long long> squares(n);
    for (int i = 0; i < n; ++i)
        squares[i] = 1LL * sticks[i] * sticks[i];

    long long acute = 0, right = 0, obtuse = 0;

    for (int i = 0; i < n - 2; ++i) {
        for (int j = i + 1; j < n - 1; ++j) {
            int sum = sticks[i] + sticks[j];
            long long squareSum = squares[i] + squares[j];

            int left = j + 1, rightIdx = n - 1, k = j;
            while (left <= rightIdx) {
                int mid = (left + rightIdx) / 2;
                if (sticks[mid] < sum) {
                    k = mid;
                    left = mid + 1;
                } else {
                    rightIdx = mid - 1;
                }
            }

            if (k == j) continue;


            auto rightPos = lower_bound(squares.begin() + j + 1, squares.begin() + k + 1, squareSum);
            bool isRight = (rightPos != squares.begin() + k + 1 && *rightPos == squareSum);

            int acuteCount = rightPos - (squares.begin() + j + 1);
            acute += acuteCount;
            if (isRight) right++;
            obtuse += (k - j - acuteCount - isRight);
        }
    }

    cout << acute << " " << right << " " << obtuse << endl;
}

int main() {
    int n;
    cin >> n;
    vector<int> sticks(n);
    for (int i = 0; i < n; ++i)
        cin >> sticks[i];

    countTriangles(sticks);
    return 0;
}