ZeroJudge B557: 直角三角形

題目敘述

每筆測資第一行有一個正整數T，接下來會有T筆資料，每筆資料第一行會有一個正整數N，第二行有N個正整數代表不同長度的木棒。要求輸出每一筆資料中可以生成幾組直角三角形。

範例輸入 #1

3

3

3 4 5

6

3 3 4 4 5 5

3

3 4 6

範例輸出 #1

1

8

0

解題思路

收資料的時候同一個數字只需收一次，但是要用Map紀錄這個數字出現的次數，並且存放到陣列的時候可以先將資料進行平方。將陣列排序過後使用兩個For迴圈來取陣列中的任意兩數，代表 a^2 + b^2 = c^2 的a和b。只需判斷c是否在Map中有超過一個數量就可以判斷這樣的組合是否為直角三角形。因為同一個數字可能會超過一個，所以答案要 += MAP[a] * MAP[b] * MAP[c]。

解題程式碼如下 (僅供參考)：

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 0; i<T; i++)
    {
        vector<int>num;
        map<int, int>MAP;
        int N, ans = 0;
        cin >> N;
        for (int j = 0; j<N; j++)
        {
            int tmp;
            cin >> tmp;
            tmp = pow(tmp, 2);
            if (MAP[tmp] == 0) num.push_back(tmp);
            MAP[tmp]++;
        }
        sort(num.begin(), num.end());
        for (int j = 0; j<num.size(); j++)
        {
            for (int k = j+1; k<num.size(); k++)
            {
                int c = num[j] + num[k];
                if (MAP[c] > 0) ans += MAP[num[j]] * MAP[num[k]] * MAP[c];
            }
        }
        cout << ans << "\n";
    }
}