Tìm số cặp (hypotenuse, area) tạo tam giác vuông bằng C++

Cho mảng H[] (các giá trị huyền) và A[] (các giá trị diện tích). Đếm số cặp (H, A) có thể tạo thành tam giác vuông với huyền H và diện tích A.

Công thức toán học

Tam giác vuông cạnh góc vuông x, y, huyền H, diện tích A:

• A = (x·y)/2 → 4A² = (x·y)²
• x² + y² = H²

Ví dụ

Input: H[] = {3, 6, 8}, A[] = {2, 31, 12} Output: 4
Các cặp: (3,2), (6,2), (8,2), (8,12)

Input: H[] = {2, 5, 9}, A[] = {3, 11, 7} Output: 4
Các cặp: (5,3), (9,3), (9,11), (9,7)

Phương pháp Brute Force

Kiểm tra tất cả cặp (H[i], A[j]), đếm nếu H[i]² ≥ 4·A[j]. Độ phức tạp O(N²).

Mã nguồn Brute Force

#include <iostream>
using namespace std;

int main() {
    int H[] = {2, 5, 9};
    int s1 = sizeof(H) / sizeof(H[0]);
    int A[] = {3, 11, 7};
    int s2 = sizeof(A) / sizeof(A[0]);
    int count = 0;

    for (int i = 0; i < s1; i++)
        for (int j = 0; j < s2; j++)
            if (H[i] * H[i] >= 4 * A[j])
                count++;

    cout << "Số cặp (H, A): " << count;
    return 0;
}

Kết quả

Số cặp (H, A): 4

Phương pháp hiệu quả (Sort + Binary Search)

Sắp xếp cả hai mảng tăng dần. Với mỗi H[i], dùng binary search trên A[] tìm chỉ số lớn nhất mid sao cho H[i]² ≥ 4·A[mid]. Số cặp hợp lệ với H[i] là mid + 1. Độ phức tạp O(N log N).

Mã nguồn hiệu quả

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

int main() {
    int H[] = {2, 5, 9};
    int s1 = sizeof(H) / sizeof(H[0]);
    int A[] = {3, 11, 7};
    int s2 = sizeof(A) / sizeof(A[0]);
    int count = 0;

    sort(H, H + s1);
    sort(A, A + s2);

    for (int i = 0; i < s1; i++) {
        int flag1 = 0, flag2 = s2 - 1, temp = -1;
        while (flag1 <= flag2) {
            int mid = flag1 + (flag2 - flag1) / 2;
            if (H[i] * H[i] >= 4 * A[mid]) {
                temp = mid;
                flag1 = mid + 1;
            } else {
                flag2 = mid - 1;
            }
        }
        if (temp != -1)
            count += temp + 1;
    }
    cout << "Số cặp (H, A): " << count;
    return 0;
}

Kết quả

Số cặp (H, A): 4

Kết luận

Bài viết giải quyết bài toán đếm cặp (huyền, diện tích) tạo tam giác vuông. Điều kiện cần đủ: H² ≥ 4A. So sánh Brute Force O(N²) và Sort+Binary Search O(N log N). Mã C++ đầy đủ.