C++ Tìm số tam giác từ tập điểm trên ba đường thẳng

Cho số điểm trên 3 đường thẳng, hãy tìm số tam giác có thể tạo thành từ các điểm này. Ví dụ:

Input: m = 3, n = 4, k = 5 → Output: 205
Input: m = 2, n = 2, k = 1 → Output: 10

Áp dụng tổ hợp toán học để xây dựng công thức giải.

Phương pháp giải

Tổng số cách chọn 3 điểm từ (m+n+k) điểm là C(m+n+k, 3). Tuy nhiên, 3 điểm thẳng hàng không tạo thành tam giác. Số bộ 3 điểm thẳng hàng trên mỗi đường là C(m,3), C(n,3), C(k,3). Do đó:

Số tam giác = C(m+n+k, 3) - C(m,3) - C(n,3) - C(k,3)

Ví dụ minh họa

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

long long fact(long long n) {
    if (n <= 1) return 1;
    return ((n % MOD) * (fact(n-1) % MOD)) % MOD;
}

long long comb(int n, int r) {
    return (((fact(n)) % MOD) / ((fact(r) % MOD) * (fact(n-r) % MOD)) % MOD);
}

int main() {
    int n = 3, m = 4, r = 5;
    long long linen = comb(n, 3);
    long long linem = comb(m, 3);
    long long liner = comb(r, 3);
    long long answer = comb(n + m + r, 3);
    answer -= (linen + linem + liner);
    cout << answer << "\n";
    return 0;
}

Kết quả

205

Giải thích

Tính tổ hợp chập 3 của tổng số điểm, trừ đi tổ hợp chập 3 của từng đường thẳng (các điểm thẳng hàng). Kết quả là số tam giác hợp lệ.

Kết luận

Đã giải bài toán số tam giác từ điểm trên 3 đường thẳng bằng tổ hợp. Chương trình C++ có thể viết bằng C, Java, Python. Hy vọng hữu ích.