C++ এ m সমরেখা সহ মোট n বিন্দু সহ ত্রিভুজের গণনা

আমাদেরকে n এবং m দুটি ভেরিয়েবল দেওয়া হয়েছে যা একটি 2D সমতলে বিন্দুর সংখ্যা উপস্থাপন করে। n বিন্দুর মধ্যে, m বিন্দু সমরেখার। লক্ষ্য হল এই n বিন্দু ব্যবহার করে ত্রিভুজের সংখ্যা খুঁজে বের করা।

সমলাইন বিন্দু − একই রেখায় অবস্থিত বিন্দুগুলিকে সমরেখা বলা হয়। বিন্দু A এবং B সমরেখার।

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

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

4 =4C₃ এর মধ্যে যেকোনো তিনটি বিন্দু নির্বাচন করা

কিন্তু সমরেখার বিন্দু ত্রিভুজ গঠন করতে পারে না তাই সম্ভাব্য ত্রিভুজগুলি সরিয়ে ফেলুন যা উপরে গণনা করা হবে =2C₃

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

n এবং m =nC₃-এর জন্য - mC₃

আসুন উদাহরণ দিয়ে বুঝতে পারি।

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

আউটপুট − m সমরেখা সহ মোট n বিন্দু সহ ত্রিভুজের সংখ্যা হল − 9

ব্যাখ্যা − মোট ত্রিভুজ =5C₃ - 3C₃ =10 - 1 =9

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

আউটপুট − m সমরেখা সহ মোট n বিন্দু সহ ত্রিভুজের সংখ্যা হল − 110

ব্যাখ্যা − মোট ত্রিভুজ =10C₃ - 5C₃ =120 - 10 =110

নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি

সমন্বয়ের গণনা ধারণ করার জন্য আমরা একটি প্যাসকেল ত্রিভুজ তৈরি করব। প্রতিটি সারি পূর্ববর্তী সারি কলাম যোগ করে গণনা করা হয়।

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

উদাহরণ

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

আউটপুট

যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −

উৎপন্ন করবে

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