C++ তে অ্যাঙ্গুলার সুইপ অ্যালগরিদম (Angular Sweep Algorithm)

অ্যাঙ্গুলার সুইপ অ্যালগরিদম দিয়ে একটি নির্দিষ্ট ত্রিজ্যায় (r) কতটিমাত্রা ২D পয়েন্ট একটি বৃত্তের ভেতর আনা যায়, সেটি বের করা হয়।

অ্যালগরিদম

সব পয়েন্ট জোড়ার মধ্যকে দূরত্ব বের করুন (ⁿC₂)।
একটি পয়েন্ট P ধরে সেটিকে কেন্দ্র করে বৃত্ত ঘুরিয়ে ম্যাক্সিমাম পয়েন্ট কাউন্ট করুন।
সর্বোচ্চ পয়েন্ট সংখ্যা রিটার্ন করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;
#define MAX_POINTS 500
typedef complex<double> Point;
Point arr[MAX_POINTS];
double dis[MAX_POINTS][MAX_POINTS];

int getPointsInside(int i, double r, int n) {
    vector<pair<double, bool>> angles;
    for (int j = 0; j < n; j++) {
        if (i != j && dis[i][j] <= 2*r) {
            double B = acos(dis[i][j]/(2*r));
            double A = arg(arr[j]-arr[i]);
            double alpha = A-B, beta = A+B;
            angles.push_back({alpha, true});  // entry
            angles.push_back({beta, false});  // exit
        }
    }
    sort(angles.begin(), angles.end());
    int count = 1, res = 1;
    for (auto &it : angles) {
        if (it.second) count++; else count--;
        res = max(res, count);
    }
    return res;
}

int maxPoints(Point arr[], int n, int r) {
    for (int i = 0; i < n-1; i++)
        for (int j=i+1; j < n; j++)
            dis[i][j] = dis[j][i] = abs(arr[i]-arr[j]);
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, getPointsInside(i, r, n));
    return ans;
}

int main() {
    Point arr[] = {Point(6.47634, 7.69628), Point(5.16828, 4.79915), Point(6.69533, 6.20378)};
    int r = 1, n = sizeof(arr)/sizeof(arr[0]);
    cout << "The maximum number of points are: " << maxPoints(arr, n, r);
    return 0;
}

আউটপুট

The maximum number of points are: 2