মোট n বিন্দু এবং m সংরেখ বিন্দু দিয়ে ত্রিভুজের গণনা (C++ প্রোগ্রাম)

আমাদের দুটি ভেরিয়েবল n এবং m দেওয়া আছে যা ২D প্লেনে বিন্দুর সংখ্যা নির্দেশ করে। n বিন্দুর মধ্যে m বিন্দু সংরেখ (collinear)। লক্ষ্য হল এই n বিন্দু ব্যবহার করে কতগুলো ত্রিভুজ তৈরি করা যায় সেটি বের করা।

সংরেখ বিন্দু (Collinear points): একই রেখায় অবস্থিত বিন্দুগুলোকে সংরেখ বিন্দু বলে। বিন্দু A এবং B সংরেখ।

দেওয়া n=4 (A,B,C,D), m=2 (A,B)

ত্রিভুজের সংখ্যা:

৪ বিন্দু থেকে যেকোনো ৩টি বেছে নেওয়া = ⁴C₃

কিন্তু সংরেখ বিন্দু ত্রিভুজ তৈরি করতে পারে না তাই উপরের হিসাব থেকে সম্ভাব্য ত্রিভুজ বাদ দিতে হবে = ²C₃

মোট ত্রিভুজ = ⁴C₃ - ²C₃ = 4 - 0 = 4 (ABC, ACD, BCD, ABD)

সাধারণত n এবং m এর জন্য = nC₃ - mC₃

ইনপুট: n=5, m=3

আউটপুট: মোট n বিন্দু এবং m সংরেখ বিন্দু দিয়ে ত্রিভুজের গণনা: 9

ব্যাখ্যা: মোট ত্রিভুজ = ⁵C₃ - ³C₃ = 10 - 1 = 9

ইনপুট: n=10, m=5

আউটপুট: মোট n বিন্দু এবং m সংরেখ বিন্দু দিয়ে ত্রিভুজের গণনা: 110

ব্যাখ্যা: মোট ত্রিভুজ = ¹⁰C₃ - ⁵C₃ = 120 - 10 = 110

আমরা প্যাসকালের ত্রিভুজ (pascal triangle) তৈরি করব কম্বিনেশন (combination) হিসাবের জন্য। প্রতিটি সারি আগের সারির কলাম যোগ করে হিসাব করা হয়।

• n এবং m ইনপুট নিন বিন্দুর সংখ্যা হিসেবে।
• collinear_points(int n,int m) ফাংশন n এবং m নেয় এবং মোট n বিন্দু এবং m সংরেখ বিন্দু দিয়ে ত্রিভুজের গণনা ফেরত দেয়।
• count = check(n, 3) - check(m, 3) সেট করুন (nC₃ - mC₃ হিসাবের জন্য)।
• check(int n, int r) ফাংশন n এবং r নেয় এবং nCᵣ এর মান ফেরত দেয়।
• r+1 দৈর্ঘ্যের একটি অ্যারে arr নিন।
• memset দিয়ে পুরো অ্যারে ০ দিয়ে আরম্ভিক করুন।
• arr[0] = 1 সেট করুন।
• দুটি for লুপ দিয়ে i=1 থেকে i<=n এবং j=min(i,r) থেকে j>0 পর্যন্ত প্যাসকালের ত্রিভুজ হিসাব করুন arr[j]=arr[j]+arr[j-1]।
• শেষে arr[r]-এ nCᵣ এর মান পাওয়া যাবে। এটিকে ফেরত দিন।
• check() ফাংশন শেষে ত্রিভুজের গণনা পাওয়া যাবে।
• ফলাফল হিসেবে count ফেরত দিন।

#include 
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;
}

Count of triangles with total n points with m collinear are: 20