Thuật toán Angular Sweep trong C++

Angular Sweep (Quét góc) – Tìm số điểm tối đa nằm trong một đường tròn bán kính R cho trước từ tập điểm 2D.

Ý tưởng

• Với mỗi điểm P làm tâm quay, xét các điểm khác trong bán kính 2R.
• Tính góc của các cung (arc) mà tâm đường tròn bán kính R có thể đặt để bao chứa điểm đó.
• Dùng kỹ thuật "sweep line" trên góc: sắp xếp các sự kiện bắt đầu/kết thúc cung, đếm số cung chồng chéo tối đa.

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

using Point = complex<double>;
const int MAXN = 500;
Point pts[MAXN];
double dist[MAXN][MAXN];

int getPointsInside(int i, double r, int n) {
    vector<pair<double, bool>> events; // {góc, true=bắt đầu, false=kết thúc}
    for (int j = 0; j < n; j++) if (i != j && dist[i][j] <= 2*r) {
        double B = acos(dist[i][j] / (2*r));
        double A = arg(pts[j] - pts[i]); // góc vectơ từ i đến j
        events.push_back({A - B, true});
        events.push_back({A + B, false});
    }
    sort(events.begin(), events.end());
    int cnt = 1, res = 1; // điểm i luôn nằm trong
    for (auto &e : events) {
        if (e.second) cnt++; else cnt--;
        res = max(res, cnt);
    }
    return res;
}

int maxPoints(Point pts[], int n, double r) {
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            dist[i][j] = dist[j][i] = abs(pts[i] - pts[j]);
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, getPointsInside(i, r, n));
    return ans;
}

int main() {
    Point pts[] = {{6.47634, 7.69628}, {5.16828, 4.79915}, {6.69533, 6.20378}};
    int n = 3, r = 1;
    cout << "So diem toi da trong duong tron: " << maxPoints(pts, n, r);
    return 0;
}

Kết quả

So diem toi da trong duong tron: 2