資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告