একটি প্রদত্ত ব্যাসার্ধের একটি বৃত্তে আবদ্ধ হতে পারে এমন সর্বাধিক সংখ্যক বিন্দু খুঁজে বের করার অ্যালগরিদম। এর মানে হল r ব্যাসার্ধের একটি বৃত্ত এবং 2-D বিন্দুর একটি প্রদত্ত সেটের জন্য, আমাদেরকে বৃত্ত দ্বারা আবদ্ধ (বৃত্তের ভিতরে ধারে নয়) সর্বাধিক সংখ্যক বিন্দু খুঁজে বের করতে হবে৷
জন্য, এটি সবচেয়ে কার্যকর পদ্ধতি হল কৌণিক সুইপ অ্যালগরিদম।
অ্যালগরিদম
-
আছে n C2 সমস্যায় দেওয়া পয়েন্ট, আমাদের এই প্রতিটি বিন্দুর মধ্যে দূরত্ব খুঁজে বের করতে হবে।
-
একটি স্বেচ্ছাচারী বিন্দু নিন এবং P বিন্দুটি ঘোরানোর সময় বৃত্তে থাকা সর্বাধিক সংখ্যক বিন্দু পান .
-
সমস্যার চূড়ান্ত রিটার্ন মান হিসাবে আবদ্ধ করা যেতে পারে এমন সর্বাধিক সংখ্যক পয়েন্ট ফেরত দেওয়া।
উদাহরণ
#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;
double beta = A+B;
angles.push_back(make_pair(alpha, true));
angles.push_back(make_pair(beta, false));
}
}
sort(angles.begin(), angles.end());
int count = 1, res = 1;
vector <pair<double, bool>>::iterator it;
for (it=angles.begin(); it!=angles.end(); ++it) {
if ((*it).second)
count++;
else
count--;
if (count > res)
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;
int 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
