Đếm số tam giác từ n điểm với m điểm thẳng hàng trong C++

Cho hai biến n và m biểu thị số điểm trên mặt phẳng 2D. Trong n điểm, có m điểm thẳng hàng. Mục tiêu là tìm số tam giác có thể tạo bằng n điểm này.

Điểm thẳng hàng (Collinear) - Các điểm nằm trên cùng một đường thẳng.

Ví dụ: n=4 (A,B,C,D), m=2 (A,B)

Số tam giác = Chọn 3 điểm bất kỳ trong 4 = 4C₃

Nhưng điểm thẳng hàng không tạo thành tam giác, loại bỏ = 2C₃

Tổng tam giác = 4C₃ - 2C₃ = 4 - 0 = 4 (ABC, ACD, BCD, ABD)

Công thức chung: nC₃ - mC₃

Ví dụ

Đầu vào - n=5, m=3

Đầu ra - Số tam giác là 9

Giải thích - 5C₃ - 3C₃ = 10 - 1 = 9

Đầu vào - n=10, m=5

Đầu ra - Số tam giác là 110

Giải thích - 10C₃ - 5C₃ = 120 - 10 = 110

Phương pháp sử dụng

Tạo tam giác Pascal để tính tổ hợp. Mỗi hàng tính bằng cộng hai ô hàng trước.

• Nhập n, m
• Hàm collinear_points(int n, int m) trả về số tam giác
• count = check(n, 3) - check(m, 3)
• Hàm check(int n, int r) tính nC_r
• Mảng arr độ dài r+1, khởi tạo 0, arr[0] = 1
• Hai vòng lặp i=1 đến n, j=min(i,r) đến 1: arr[j] = arr[j] + arr[j-1]
• Trả về arr[r]
• Trả về count

Chương trình minh họa

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

int check(int n, int r) {
    int arr[r+1];
    memset(arr, 0, sizeof(arr));
    arr[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = min(i, r); j > 0; j--)
            arr[j] = arr[j] + arr[j-1];
    }
    return arr[r];
}

int collinear_points(int n, int m) {
    int count = check(n, 3) - check(m, 3);
    return count;
}

int main() {
    int n = 6, m = 2;
    cout << "Số tam giác từ n điểm với m điểm thẳng hàng là: " << collinear_points(n, m);
    return 0;
}

Đầu ra

Số tam giác từ n điểm với m điểm thẳng hàng là: 20