ZeroJudge B557: Right Triangle

You have N sticks of varying lengths today, and you want to know how many "right-angled triangles" you can form with these sticks.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains a number T, representing the number of test cases (1 ≤ T ≤ 50).
Each test case consists of two lines:
The first line contains a number N, indicating the number of sticks (1 ≤ N ≤ 100).
The second line contains N numbers ai separated by spaces, representing the lengths of the sticks (1 ≤ ai ≤ 100).		For each test case, output one line containing a number x, representing how many right-angled triangles can be formed.
3
3
3 4 5
6
3 3 4 4 5 5
3
3 4 6		1
8
0

Thought Process

When collecting the data, each number only needs to be collected once, but you should use a map to record the number of times this number appears, and when storing the data in an array, you can first square the data.

After sorting the array, use two for loops to select any two numbers from the array, representing a and b in the equation a^2 + b^2 = c^2. It is only necessary to check if c appears more than once in the Map to determine if such a combination forms a right-angled triangle.

Since the same number may appear more than once, the answer should be incremented by MAP[a] * MAP[b] * MAP[c].

Sample Code－ZeroJudge B557: Right Triangle

#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";
    }
}

//ZeroJudge B557
//Dr. SeanXD
Tags

Related Posts

Comments