อัลกอริธึมในการค้นหาจำนวนจุดสูงสุดที่สามารถอยู่ในวงกลมของรัศมีที่กำหนด ซึ่งหมายความว่าสำหรับวงกลมรัศมี r และชุดจุด 2 มิติที่กำหนด เราจำเป็นต้องหาจำนวนจุดสูงสุดที่ล้อมรอบด้วยวงกลม (อยู่ในวงกลมไม่ได้อยู่ที่ขอบ)
สำหรับวิธีนี้เป็นวิธีที่ได้ผลมากที่สุดคืออัลกอริธึมการกวาดเชิงมุม
อัลกอริทึม
-
มี 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
