किसी दिए गए त्रिज्या के एक सर्कल में संलग्न किए जा सकने वाले बिंदुओं की अधिकतम संख्या को खोजने के लिए एल्गोरिदम। इसका मतलब यह है कि त्रिज्या r के एक वृत्त और 2-डी बिंदुओं के दिए गए सेट के लिए, हमें वृत्त द्वारा संलग्न बिंदुओं की अधिकतम संख्या ज्ञात करनी होगी (वृत्त के अंदर इसके किनारों पर नहीं)।
के लिए, यह सबसे प्रभावी तरीका है कोणीय स्वीप एल्गोरिथ्म।
एल्गोरिदम
-
n . हैं सी<उप>2 समस्या में दिए गए बिंदुओं के लिए, हमें इनमें से प्रत्येक बिंदु के बीच की दूरी ज्ञात करनी होगी।
-
एक मनमाना बिंदु लें और उस बिंदु के बारे में घुमाए जाने पर वृत्त में पड़े अधिकतम अंक प्राप्त करें 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