Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 각도 스윕(Angular Sweep) 알고리즘: 반지름 r인 원 안에 포함되는 최대 점 개수 구하기

주어진 반지름 r을 가진 원과 2차원 평면 위의 여러 점들이 있을 때, 그 원이 품을 수 있는 최대 점 개수를 찾는 것이 이 글의 핵심 문제입니다. 여기서 '포함된다'는 것은 점이 원의 경계선이 아니라 원의 내부에 위치한다는 의미입니다.

이 문제를 해결하는 가장 효율적인 방법 중 하나가 바로 각도 스윕(Angular Sweep) 알고리즘입니다.

알고리즘 동작 원리

  • 문제에 주어진 n개의 점에 대해 서로 다른 두 점으로 만들 수 있는 모든 쌍(nC2) 사이의 거리를 미리 계산해 둡니다.

  • 임의의 한 점 P를 기준점으로 선택합니다. 어떤 점 j가 반지름 r인 원의 내부에 들어오려면, 그 원의 중심은 점 j를 중심으로 하는 반지름 r짜리 원과의 교차 영역 안에 있어야 합니다. 두 점 사이의 거리를 d라고 할 때, 아크코사인 함수를 이용해 acos(d / (2r)) 값을 구하면 원이 점 j를 덮기 시작하는 진입 각도(alpha)와 덮음이 끝나는 이탈 각도(beta)를 계산할 수 있습니다. 이때 거리가 2r보다 큰 점들은 어떤 원의 중심 위치와 무관하게 절대 포함될 수 없으므로 제외합니다.

  • 모든 각도 이벤트(진입/이탈)를 하나의 리스트에 넣고 오름차순으로 정렬한 뒤 순서대로 훑으면서, 진입 시에는 카운트를 증가시키고 이탈 시에는 감소시킵니다. 이 과정에서 기록된 카운트의 최댓값이 해당 기준점 P에서 얻을 수 있는 결과입니다.

  • 모든 점을 차례로 기준점으로 삼아 위 과정을 반복하고, 그중 가장 큰 값을 문제의 최종 답으로 반환합니다.

C++ 구현 예제

#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;
}

코드 설명

  • Point는 complex<double> 타입으로 정의되어 복소수 연산만으로 두 점 사이의 유클리드 거리(abs)와 편각(arg)을 손쉽게 구할 수 있습니다.

  • getPointsInside 함수는 특정 기준점 i에 대해, 거리가 2r 이하인 점들의 진입/이탈 각도 이벤트를 생성하고 정렬한 뒤 스윕하여 해당 위치에서 원이 포함할 수 있는 최대 점 수를 반환합니다.

  • maxPoints 함수는 모든 점 쌍 간 거리를 미리 계산해 두고, 각 점을 기준점으로 삼아 결과의 최댓값을 구합니다.

실행 결과

The maximum number of points are: 2

예제에서는 세 개의 점과 반지름 1인 원이 주어졌으며, 원을 적절히 배치했을 때 내부에 포함할 수 있는 점의 최대 개수는 2개임을 확인할 수 있습니다.

시간 복잡도

각 기준점마다 최대 n-1개의 점에 대해 각도 이벤트를 만들고 정렬하므로, 전체 시간 복잡도는 O(n² log n)입니다. 완전 탐색(O(n³))에 비해 훨씬 효율적이며, 점의 개수가 수백~수천 수준일 때도 실용적으로 동작합니다.