Subtask 1

Với \(N = 3\), sẽ chỉ có tối đa 1 tam giác duy nhất để xét. Ta chỉ cần kiểm tra tam giác này là xong
Gọi 3 cạnh của 1 tam giác là \(A \leq B \leq C\), ta có:
1) ABC là tam giác nhọn khi \(A^2 + B^2>C^2\)
2) ABC là tam giác vuông khi \(A^2 + B^2=C^2\)
3) ABC là tam giác tù khi \(A^2 + B^2<C^2\) và \(A+B>C\)

Time: \(O(1)\)
Space: \(O(1)\)

Subtask 2

Với \(N \leq 300\), ta có thể duyệt qua tất cả bộ 3 độ dài cạnh tam giác và kiểm tra tương tự subtask 1

Time: \(O(N^3)\)
Space: \(O(N)\)

Reference Code:
```cpp=

include <bits/stdc++.h>

define fu(i, a, b) for (long long i = (a); i <= (b); i++)

define fd(i, a, b) for (long long i = (a); i >= (b); i--)

using namespace std;
typedef long long ll;
const ll N = 3e3 + 10;
ll n, K, a[N];
int main()
{
cin >> n >> K;
fu(i, 1, n) cin >> a[i];
sort(a + 1, a + n + 1);
ll nhon = 0, vuong = 0, tu = 0;
fu(i, 1, n - 2)
{
fu(j, i + 1, n - 1)
{
fu(k, j + 1, n)
{
ll A = a[i], B = a[j], C = a[k];
if (A * A + B * B > C * C) nhon++;
if (A * A + B * B == C * C) vuong++;
if (A * A + B * B < C * C && A + B > C) tu++;
}
}
}
if (K == 1) cout << nhon;
if (K == 2) cout << vuong;
if (K == 3) cout << tu;
}

Subtask 3

Ở subtask cuối, \(N \leq 3000\), ta có thể sắp xếp mảng trước. Duyệt các bộ \(i < j\), ta sẽ có \(A = a[i], B = a[j]\) và sử dụng kỹ thuật Hai con trỏ để tìm các vị trí \(k > j\) mà \(C = a[k]\) thỏa mãn.
Cụ thể hơn, ta sẽ cần tìm 3 vị trí:
1) Vị trí nhỏ nhất mà \(C^2\geq A^2+B^2\), ở đây ta gọi là \(l\)
2) Vị trí nhỏ nhất mà \(C^2>A^2+B^2\), ở đây ta gọi là \(r\)
3) Vị trí nhỏ nhất mà \(C>A+B\), ở đây ta gọi là \(limit\)

• Nếu C nằm trong khoảng từ \(j+1\) tới \(l-1\) thì \(ABC\) là tam giác nhọn
• Nếu C nằm trong khoảng từ \(l\) tới \(r-1\) thì \(ABC\) là tam giác vuông
• Nếu C nằm trong khoảng từ \(r\) tới \(limit-1\) thì \(ABC\) là tam giác tù

  Time: \(O(N^2)\)
  Space: \(O(N)\)
  Reference Code:
  ```cpp=

include <bits/stdc++.h>

define fu(i, a, b) for (long long i = (a); i <= (b); i++)

define fd(i, a, b) for (long long i = (a); i >= (b); i--)

using namespace std;
typedef long long ll;
const ll N = 3e3 + 10;
ll n, K, a[N];
int main()
{
cin >> n >> K;
fu(i, 1, n) cin >> a[i];
sort(a + 1, a + n + 1);
ll nhon = 0, vuong = 0, tu = 0;
fu(i, 1, n - 2)
{
ll l = i + 2, r = i + 2, lim = i + 2;
fu(j, i + 1, n - 1)
{
while (l <= n && a[l] * a[l] < a[i] * a[i] + a[j] * a[j]) l++;
while (r <= n && a[r] * a[r] <= a[i] * a[i] + a[j] * a[j]) r++;
while (lim <= n && a[lim] < a[i] + a[j]) lim++;
nhon += l - j - 1;
vuong += r - l;
tu += lim - r;
}
}
if (K == 1) cout << nhon;
if (K == 2) cout << vuong;
if (K == 3) cout << tu;
}