อัลกอริทึม Angular Sweep ใน C++

อัลกอริทึมหาจำนวนจุดสูงสุดที่อยู่ภายในวงกลมรัศมีกำหนด สำหรับวงกลมรัศมี r และชุดจุด 2D ให้หาจุดสูงสุดที่อยู่ภายในวงกลม (ไม่รวมจุดบนขอบ)

วิธีที่มีประสิทธิภาพที่สุดคือ Angular Sweep Algorithm

อัลกอริทึม

• มี ⁿC₂ จุด หาระยะห่างระหว่างทุกคู่จุด
• เลือกจุดสุ่มหนึ่งจุด หาจุดสูงสุดที่อยู่ในวงกลมเมื่อหมุนรอบจุด 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;
    for (auto 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