অনুভূমিক এবং উল্লম্ব রেখার অংশগুলির মধ্যে ত্রিভুজের সংখ্যা খুঁজে পেতে C++ প্রোগ্রাম

এই প্রবন্ধে, আমরা প্রদত্ত অনুভূমিক এবং উল্লম্ব রেখার ছেদ বিন্দুতে যোগদানের মাধ্যমে ত্রিভুজের সংখ্যা খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব।

উদাহরণস্বরূপ, আসুন আমরা বলি যে আমাদের নিম্নলিখিত লাইনের অংশগুলি দেওয়া হয়েছিল। এতে আমাদের 3টি ইন্টারসেকশন পয়েন্ট আছে। সুতরাং এই বিন্দুগুলি ব্যবহার করে যে ত্রিভুজগুলি তৈরি করা যেতে পারে তার সংখ্যা হবে ³ C₂ .

আমরা সুইপ লাইন অ্যালগরিদম অনুসরণ করব। আমরা লাইন সেগমেন্টের সমস্ত মান সংরক্ষণ করব এবং তারপর পরীক্ষা করব যে একটি লাইনের ভিতরের পয়েন্টগুলি অন্য কোনও লাইনের অভ্যন্তরীণ বিন্দুর সাথে তুলনা করে কিনা। এইভাবে আমরা প্রদত্ত রেখার অংশগুলির জন্য সমস্ত ছেদ বিন্দু পেতে পারি এবং তারপরে বিভিন্ন সম্ভাব্য সংমিশ্রণ ব্যবহার করে আমরা সহজেই সম্ভাব্য ত্রিভুজের সংখ্যা খুঁজে পেতে পারি।

উদাহরণ

#include#define maxy 1000005#define maxn 10005using namespace std;// to store intersection pointsstruct i_point { int x, y; i_point(int a, int b) { x =a, y =b; }};int bit[maxy];vector > events;//প্রদত্ত পয়েন্টগুলিকে সাজাতে com_points(pair &a, pair &b) { if ( a. first.x !=b.first.x ) ফেরত a.first.x  0) { res +=bit[index]; index -=index &(-index); } রিটার্ন রেস;}// একটি লাইন সেগমেন্টভয়েড ইনসার্টলাইন (i_point a, i_point b) { // অনুভূমিক রেখার ক্ষেত্রে যদি (a.y ==b.y) { int begin =min(a.x, b.x); int end =max(a.x, b.x); events.push_back(make_pair(i_point(begin, a.y), 1)); events.push_back(make_pair(i_point(end, a.y), 2)); } // উল্লম্ব রেখার ক্ষেত্রে else { int top =max(b.y, a.y); int bottom =min(b.y, a.y); events.push_back(make_pair(i_point(a.x, top), 3)); events.push_back(make_pair(i_point(a.x, bottom), 3)); }}// ছেদ বিন্দুর সংখ্যা গণনা করতে calc_i_points() { int i_points =0; জন্য (int i =0; i =3 ) ফিরে আসে ( পয়েন্ট * (পয়েন্ট - 1) * (পয়েন্ট - 2) ) / 6; অন্যথায় রিটার্ন 0;}int main() { insertLine(i_point(3, 2), i_point(3, 13)); সন্নিবেশ লাইন(i_point(1, 5), i_point(3, 5)); সন্নিবেশ লাইন(i_point(8, 2), i_point(8, 8)); সন্নিবেশ লাইন(i_point(3, 4), i_point(6, 4)); সন্নিবেশ লাইন(i_point(4, 3), i_point(4, 5)); sort(events.begin(), events.end(), com_points); cout <<"ত্রিভুজের সম্ভাব্য সংখ্যা :" < 
আউটপুট
 
ত্রিভুজের সম্ভাব্য সংখ্যা :১