数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究C++ 中的角扫算法
该算法用于查找可被给定半径的圆形包围的最大点数。这意味着对于半径为 r的圆和给定的 2-D 点集，我们需要找到圆形包围（位于圆内，不在圆的边缘上）的最大点数。
这是最有效的方法是角扫算法。
算法
本题目中给定nC2个点，我们需要找出各个点之间的距离。
取一个任意点，围绕点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
更新于： 2019 年 10 月 4 日
411 次浏览
广告