Thuật toán tìm số điểm tối đa có thể được bao quanh trong một hình tròn bán kính cho trước. Điều này có nghĩa là đối với một đường tròn bán kính r và một tập hợp các điểm 2-D cho trước, chúng ta cần tìm số điểm tối đa mà đường tròn bao quanh (nằm bên trong đường tròn không nằm trên các cạnh của nó).
Vì, đây là phương pháp hiệu quả nhất là thuật toán quét góc.
Thuật toán
-
Có n C 2 điểm được đưa ra trong bài toán, chúng ta cần tìm khoảng cách giữa mỗi điểm này.
-
Lấy một điểm tùy ý và nhận được số điểm tối đa nằm trong hình tròn khi xoay về điểm P .
-
Trả lại số điểm tối đa có thể được bao gồm dưới dạng giá trị trả về cuối cùng của vấn đề.
Ví dụ
#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;
} Đầu ra
The maximum number of points are: 2