C++의 각도 스윕 알고리즘

주어진 반지름의 원에 포함될 수 있는 최대 점 수를 찾는 알고리즘입니다. 이것은 반지름이 r인 원과 주어진 2차원 점 집합에 대해 원으로 둘러싸인(가장자리가 아닌 원 내부에 있는) 점의 최대 수를 찾아야 함을 의미합니다.

가장 효과적인 방법은 Angular Sweep 알고리즘이기 때문입니다.

알고리즘

• ⁿ 이(가) 있습니다. 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;
   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