Tìm số lượng tam giác duy nhất trong N tam giác cho trước trong C++

Giới thiệu

Cho ba mảng s1[], s2[], s3[] kích thước N, mỗi bộ ba (s1[i], s2[i], s3[i]) đại diện cho một tam giác. Tìm số tam giác duy nhất (không có tam giác nào khác có cùng ba độ dài cạnh).

Ví dụ minh họa

Đầu vào

s1[] = {1, 5, 3}
s2[] = {2, 3, 2}
s3[] = {4, 2, 5}

Đầu ra

1

Giải thích

Tam giác (1, 2, 4) là duy nhất. Hai tam giác còn lại (5, 3, 2) và (3, 2, 5) trùng nhau sau khi sắp xếp.

Phương pháp giải

Sắp xếp ba cạnh của mỗi tam giác, lưu vào map để đếm tần suất. Tam giác duy nhất là những cái xuất hiện đúng 1 lần.

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;

int countUniqueTriangle(int a[], int b[], int c[], int n) {
    vector triSides[n];
    map, int> m;
    for (int i = 0; i < n; i++) {
        triSides[i].push_back(a[i]);
        triSides[i].push_back(b[i]);
        triSides[i].push_back(c[i]);
        sort(triSides[i].begin(), triSides[i].end());
        m[triSides[i]]++;
    }
    int uniqueTriCount = 0;
    for (auto itr = m.begin(); itr != m.end(); itr++) {
        if (itr->second == 1)
            uniqueTriCount++;
    }
    return uniqueTriCount;
}

int main() {
    int s1[] = { 1, 5 ,3 };
    int s2[] = { 2, 3, 2 };
    int s3[] = { 4, 2, 5 };
    int N = sizeof(s1) / sizeof(s1[0]);
    cout << "The number of unique triangles is " << countUniqueTriangle(s1, s2, s3, N);
    return 0;
}

Đầu ra

The number of unique triangles is 1