Chúng ta được cung cấp hai biến n và m đại diện cho số điểm trên mặt phẳng 2D. Trong số n điểm, có m điểm thẳng hàng. Mục đích là tìm số tam giác có thể được tạo thành bằng cách sử dụng n điểm này.
Điểm thu gọn - Những điểm cùng nằm trên một đường thẳng gọi là thẳng hàng. Điểm A và B thẳng hàng.
Cho n =4 (A, B, C, D), m =2 (A, B)
Số hình tam giác -
Chọn ba điểm bất kỳ trong số 4 =4C 3
Nhưng các điểm thẳng hàng không thể tạo thành tam giác, vì vậy hãy loại bỏ các tam giác có thể sẽ được tính ở trên =2C 3
Tổng số tam giác =4C 3 - 2C 3 =4-0 =4 (ABC, ACD, BCD, ABD)
Đối với n và m =nC 3 - mC 3
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - n =5, m =3
Đầu ra - Số tam giác có tổng n điểm với m thẳng hàng là - 9
Giải thích - Tổng số tam giác =5C 3 - 3C 3 =10 - 1 =9
Đầu vào - n =10, m =5
Đầu ra - Số tam giác có tổng n điểm với m thẳng hàng là - 110
Giải thích - Tổng số tam giác =10C 3 - 5C 3 =120 - 10 =110
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Chúng ta sẽ tạo một tam giác pascal để chứa các phép tính kết hợp. Mỗi hàng được tính bằng cách cộng các cột của hàng trước đó.
-
Lấy các biến n và m làm đầu vào cho một số điểm.
-
Hàm collinear_points (int n, int m) lấy n và m và trả về số lượng tam giác có tổng n điểm với m thẳng hàng.
-
Đặt count =check (n, 3) - check (m, 3); (để tính toán nC 3 - mC 3 )
-
Kiểm tra hàm (int n, int r) lấy n và r và trả về giá trị của nC r
-
Lấy một arr mảng có độ dài r + 1.
-
Đặt toàn bộ mảng bằng số 0 bằng cách sử dụng memset.
-
Đặt arr [0] =1.
-
Sử dụng hai vòng lặp for từ i =0 đến i <=n. Và j =min (i, r) đến j> 0 tính toán tam giác pascal dưới dạng arr [j] =arr [j] + arr [j-1].
-
Cuối cùng, chúng ta sẽ nhận được arr [r] là nC r . Trả lại.
-
Sau khi kết thúc kiểm tra hàm (). Chúng tôi sẽ nhận được số lượng hình tam giác
-
Kết quả là số lượt trả lại.
Ví dụ
#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<<"Count of triangles with total n points with m collinear are: "<< collinear_points(n, m);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of triangles with total n points with m collinear are: 20