C++-এ সমতল তলে পারালেলোগ্রাম গণনা: মিডপয়েন্ট পদ্ধতি

একটি সমতলে কিছু বিন্দু দেওয়া আছে। এই বিন্দুগুলো ব্যবহার করে কতটি পারালেলোগ্রাম তৈরি করা যায় তা বের করুন।

গাণিতিক আভাস

একটি চতুর্ভুজ পারালেলোগ্রাম হলে তার বিপরীত বাহুগুলো সমান্তরাল ও সমান হয়। এর মানে হলো দুই ডায়াগোনালের মিডপয়েন্ট একই।

সুতরাং, যেকোনো দুটি বিন্দু জোড়া একটি ডায়াগোনাল তৈরি করে। একই মিডপয়েন্ট वाले দুটি ডায়াগোনাল একসাথে একটি পারালেলোগ্রাম তৈরি করে।

অ্যালগরিদম

1. সব সম্ভাব্য বিন্দু জোড়া (i,j) এর জন্য মিডপয়েন্ট হিসাব করুন: mid_x = x[i]+x[j], mid_y = y[i]+y[j] (২ দিয়ে ভাগ করার প্রয়োজন নেই)।
2. প্রতিটি মিডপয়েন্ট কতবার আসেছে তা ম্যাপে কাউন্ট করুন।
3. যদি একটি মিডপয়েন্ট c বার আসে, তবে সেটি থেকে C(c,2) = c*(c-1)/2টি পারালেলোগ্রাম বने।
4. সব মিডপয়েন্টের জন্য যোগফল করুন।

C++ বাস্তবায়ন

#include 
using namespace std;

int parallelogram(int a[], int b[], int size) {
    map, int> mp;
    for (int i = 0; i < size; i++)
        for (int j = i+1; j < size; j++) {
            int mx = a[i] + a[j];
            int my = b[i] + b[j];
            mp[{mx, my}]++;
        }
    
    int count = 0;
    for (auto& it : mp) {
        int c = it.second;
        count += c * (c - 1) / 2;
    }
    return count;
}

int main() {
    int a[] = {0, 3, 1, 4, 1, 5};
    int b[] = {0, 1, 3, 4, 4, 4};
    int size = sizeof(a) / sizeof(int);
    cout << "Parallelograms: " << parallelogram(a, b, size);
    return 0;
}

উদাহরণ

বিন্দু: (0,0), (3,1), (1,3), (4,4), (1,4), (5,4)

আউটপুট: 1

সময় জটিলতা

O(n² log n) - nC2 জোড়া এবং ম্যাপ ইনসারশন।